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

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

🔢 Обчислюйте суму простих чисел, знаходьте прості в діапазоні, перевіряйте число на простоту та знаходьте 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, що може ще більше пришвидшити пошук.