Калькулятор простых чисел

Калькулятор простых чисел — сумма, количество и поиск простых

🔢 Рассчитайте сумму простых чисел, найдите простые в диапазоне, проверьте число на простоту и определите 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 — сумма двух простых (не доказано!)
• Гипотеза Римана: «миллионная» задача о распределении простых
• Пробелы между простыми: разница соседних простых в среднем растёт
• Вероятность: случайное 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, что может ещё ускорить поиск.