Як знайти просте число.

Найвідоміші способи знайти список простих чисел аж до деякого значенія-- це решето Ератосфена, Решето Сундарама і решето Аткіна. Для того, щоб перевірити, чи є дане число простим, існують тести простоти
Вам знадобиться
  • Калькулятор, аркуш паперу й олівець (ручка)
Інструкція
1
Спосіб 1. Решето Ератосфена.По цього методу, щоб знайти всі прості числа не більші певного значення Х, необхідно виписати підряд всі цілі числа від одного до Х. Візьмемо число 2 як перше просте число . Викреслимо зі списку всі числа, що діляться на 2. Потім візьмемо наступне після двійки, що не викреслене число , і викреслимо зі списку всі числа, що діляться на узяте нами число . І далі кожен раз будемо брати наступне НЕ викреслене число і викреслювати зі списку всі числа, що діляться на узяте нами число . І так до тих пір поки обраний нами число не почне більше, ніж Х/2. Всі залишилися у списку не викреслені числа є простими
2
Спосіб 2. Решето Сундарама.Із ряду натуральних чисел від 1 до N виключаються всі числа видах + у + 2ху, де індекси х (не більший у) пробігають всі натуральні значення, для яких х + у + 2ху не більш N, а саме значення х = 1, 2, ..., ((2N + 1) 1/2-1)/2 і х = у, х + 1, ..., (N-х)/(2х +1) ю. Потім кожне з решти чисел множиться на 2 і збільшується на 1. Отримана в результаті послідовність являє собою всі непарні прості числа в ряду від одного до 2N + 1.
3
Спосіб 3. Решето Аткіна.Решето Аткіна являє собою складний сучасний алгоритм знаходження всіх простих чисел до заданого значення Х. Основна суть алгоритму полягає в поданні простих чисел як цілих з непарним число м уявлень в даних квадратних формах. Окремий етап алгоритму відсіває числа, кратні квадратах простих чисел в інтервалі від 5 до Х.
4
Тести простоти.Тести простоти-- це алгоритми, що дозволяють визначити, чи є конкретне число Х простим.Одін з найпростіших, але і трудомістких тестов-- це перебір дільників. Він полягає в преборе всіх цілих чисел від 2 до квадратного кореня з Х і в обчисленні залишку від ділення Х на кожне з цих чисел. Якщо залишок від ділення числа Х на деякий число (більше 1 і менше Х) дорівнює нулю, то число Х є складовим. Якщо виявляється, що число Х неможливо скоротити без залишку на жодне з чисел, крім одиниці і самого себе, то число Х простое.Кроме цього способу існує також велика кількість інших тестів для тестування простоти числа. Більшість цих тестів є імовірнісними і використовуються в криптографії. Єдиний тест, який гарантує отримання відповіді (тест AKS) дуже складний в обчисленні, що ускладнює його практичне застосування