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