Калкулатор за прости числа

Калкулатор за прости числа - сума, брой и намиране на прости числа

🔢 Изчислете сумата на простите числа, намерете прости числа в диапазон, проверете дали число е просто, и намерете n-тото просто число. Бърз алгоритъм „Решето на Ератостен“ с визуализация.

Какво са простите числа?

Просто число е естествено число, по-голямо от 1, което не може да бъде получено чрез умножение на две по-малки естествени числа. С други думи, има точно два делителя: 1 и самото себе си.

Първите 25 прости числа

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Как да проверите дали число е просто

Метод 1 - Пробно деление:

• Проверете дали n се дели на някое число от 2 до √n
• Ако да – то е съставно (не е просто)
• Ако не – то е просто

Пример: 17 просто ли е?

• √17 ≈ 4.12, така че проверяваме делимост на 2, 3, 4
• 17 ÷ 2 = 8.5 (не се дели)
• 17 ÷ 3 = 5.67 (не се дели)
• 17 ÷ 4 = 4.25 (не се дели)
• Резултат: 17 е просто число!

Решето на Ератостен

Древен алгоритъм за намиране на всички прости числа до n:

• Стъпка 1: Избройте всички числа от 2 до n
• Стъпка 2: Отбележете 2 като просто и задраскайте всички кратни на 2
• Стъпка 3: Намерете следващото незадраскано число (3) и го отбележете като просто
• Стъпка 4: Задраскайте всички кратни на това просто число
• Стъпка 5: Повтаряйте до √n
• Резултат: Всички незадраскани числа са прости

Сума на простите числа

Сума на първите n прости числа:

• Първите 10 прости числа: 2+3+5+7+11+13+17+19+23+29 = 129
• Първите 100 прости числа: сума = 24,133
• Първите 1000 прости числа: сума = 3,682,913

Сума на простите числа до n:

• До 10: 2+3+5+7 = 17
• До 100: сума = 1,060
• До 1000: сума = 76,127

Теорема за простите числа

Броят на простите числа по-малки от n е приблизително n/ln(n):

• До 100: ~25 прости числа (реално: 25)
• До 1,000: ~145 прости числа (реално: 168)
• До 10,000: ~1,086 прости числа (реално: 1,229)
• До 100,000: ~8,686 прости числа (реално: 9,592)

Видове прости числа

Близнаци прости числа: Прости числа, които се различават с 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Прости числа на Мерсен: От вида 2ᵖ - 1, където p е просто

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Най-голямото известно просто число е от типа на Мерсен (24.8 милиона цифри!)

Прости числа на Софи Жермен: Просто число p, за което 2p+1 също е просто

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Прости числа на Ферма: От вида 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• Известни са само 5 прости числа на Ферма

Приложения на простите числа

Криптография (RSA):

• Базира се на трудността да се разложат големи числа на множители
• Използва две големи прости числа (стотици цифри)
• Защитава онлайн банкиране, имейли, уебсайтове

Хеш-таблици:

• Хеш-таблици с прост размер намаляват колизиите
• Използват се в бази данни и кеширане

Генериране на случайни числа:

• Простите числа дават по-добри псевдослучайни последователности
• Използват се в симулации и игри

Интересни факти за простите числа

• Безкрайност: Доказано от Евклид ~300 г. пр.н.е. – простите числа никога не свършват
• Празнини: Могат да бъдат произволно големи (без прости числа за милиони последователни числа)
• Хипотеза на Голдбах: Всяко четно число > 2 е сума на две прости числа (недоказано!)
• Хипотеза на Риман: Награда от 1 милион долара за доказателство за разпределението на простите числа
• Разлики между прости числа: Разликата между последователни прости числа нараства
• Вероятност: Случайно число n има ~1/ln(n) шанс да е просто

Рекорди при простите числа

• Най-голямото известно просто число: 2^82,589,933 - 1 (открито през 2018 г., 24,862,048 цифри)
• Най-големите близнаци прости числа: 2,996,863,034,895 × 2^1,290,000 ± 1
• Изчисления: GIMPS (Great Internet Mersenne Prime Search) – разпределен проект

Чести заблуди

• 1 НЕ е просто: По модерната дефиниция (нужни са точно 2 делителя)
• Не всички нечетни числа са прости: 9, 15, 21, 25... са съставни
• Формула за всички прости: Няма проста формула, която генерира всички прости числа
• Модел при простите: Няма предвидим модел (изглеждат случайни)

💡 Профи съвет: Когато проверявате дали голямо число е просто, е достатъчно да тествате делимост само до квадратния му корен! Например, за да проверите дали 997 е просто, е нужно да тествате делители само до √997 ≈ 31.6, тоест 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Ако никое от тях не дели 997 без остатък, то е просто! Тази оптимизация прави проверката много по-бърза. Също така, освен 2 и 3, всички прости числа са от вида 6k±1, което може да ускори търсенето още повече!