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

Спосіб 1. Решето Ератосфена.
За цим методом, щоб знайти всі прості числа не більші певного значення Х, необхідно виписати підряд всі цілі числа від одного до Х. Візьмемо число 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. Решето Аткіна.
Решето Аткіна являє собою складний сучасний алгоритм знаходження всіх простих чисел до заданого значення Х. Основна суть алгоритму полягає в поданні простих чисел як цілих з непарним числом уявлень в даних квадратних формах. Окремий етап алгоритму відсіває числа, кратні квадратах простих чисел в інтервалі від 5 до Х.

Тести простоти.
Тести простоти-- це алгоритми, що дозволяють визначити, чи є конкретне число Х простим.
Один з найпростіших, але і трудомістких тестов-- це перебір подільників. Він складається в преборе всіх цілих чисел від 2 до квадратного кореня з Х і в обчисленні залишку від ділення Х на кожне з цих чисел. Якщо залишок від ділення числа Х на деякий число (Більше 1 і менше Х) дорівнює нулю, то число Х є складовим. Якщо виявляється, що число Х неможливо скоротити без залишку ні на одне з чисел, крім одиниці і самого себе, то число Х просте.
Крім цього способу існує також велика кількість інших тестів для тестування простоти числа. Більшість цих тестів є ймовірними і використовуються в криптографії. Єдиний тест, який гарантує отримання відповіді (тест AKS) дуже складний в обчисленні, що ускладнює його практичне застосування