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

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

Найвідоміші способи знайти список простих чисел аж до деякого значення — це решето Ератосфена, решето Сундарама і решето Аткіна. Для того, щоб перевірити, чи є дане число простим, існують тести простоти

Вам знадобиться

Калькулятор, аркуш паперу й олівець (ручка)

Інструкція

  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) дуже складний в обчисленні, що ускладнює його практичне застосування