Знаходження простих чисел використовуючи решето Ератосфена

Просте число — натуральне ціле додатне число, що має рівно два різних натуральних дільники — одиницю і самого себе. Іншими словами, число є простим, якщо воно більше одиниці і при цьому ділиться без залишку тільки на 1 та на . Наприклад, 3 — просте число, а число 6 ні — крім 1 та 6, також ділиться на 2 і на 3.

Таблиця простих чисел до 1000

Натуральні числа, які являються більшими одиниці і не є простими, називаються складеними. Таким чином, всі натуральні числа розбиваються на три класи: одиницю (має один натуральний дільник), прості числа (мають два натуральних дільники) і складені числа (мають більше двох натуральних дільників).

Найпростішим способом побудови послідовності простих чисел є алгоритм перевірки числа на простоту. Основна його суть полягає в наступному: якщо число менше 4, то воно просте; якщо більше, то послідовно перевіряється чи ділиться число без залишку на цілі числа від 2 до цілої частини квадратного кореня з числа що перевіряється. Якщо не ділиться, то число просте.

Зазначимо, що наведений алгоритм нескладний, але для визначення простоти дуже великих чисел він практично не використовується — вимагає великого часу для роботи. Тому для великих чисел — число знаків яких перевищує 100, створені більш ефективні алгоритми. Один з таких алгоритмів був запропонований давньогрецьким математиком Ератосфеном Киренським, який називається решето Ерастофена. Розглянемо основну його суть.

Отже, для початку, припустимо, що нам потрібно встановити, які з чисел є простими. Для цього, складемо список, що містить послідовність чисел від 2 до  і викреслимо кожне друге число, що міститься за числом 2. Зазначимо, що всі вони являються складеними — кратні числу 2. Перше з списку невикреслених чисел являється число 3 — відноситься до класу простих чисел. Викреслимо кожне третє число, що слідує за даним числом. В результаті, першим з невикресленим числом є 5 — також буде простим. За тим же принципом викреслимо кожне п'яте число, що міститься за числом 5. Продовжуючи аналогічні дії далі і роблячи це до тих пір, поки в списку існують числа, які можна видалити, отримаємо список який міститиме тільки прості числа.

Зауваження: на практиці, алгоритм «решето Ератосфена» можна трохи поліпшити в такий спосіб: на кожному з проходів, числа можна викреслювати, починаючи відразу з числа , тому що всі складені числа менші за число  вже будуть викреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли  стане більше, ніж значення , округлене до цілого числа в нижню сторону. На математичній мові це записується як .

Прості числа використовуючи решето Ератосфена  - приклад знаходження:

Використання описанний вище алгоритму, знайти всі прості числа, що не перевищують .

Для цього, на перщому кроці, складемо список, що містить послідовність чисел від 2 до 35.

Список цілих чисел від 2 до 35

Перше число в списку, 2 — просте. Пройдемо по складеному списку чисел, закреслюючи всі числа, кратні 2, тобто, кожне друге, починаючи з . В результаті отримаємо:

Решето Ератосфена — ітерація №1

Наступне невикреслене число, 3 — просте. Знову-таки пройдемо по списку, закреслюючи всі числа, кратні 3, тобто кожне третє, починаючи з :

Решето Ератосфена — ітерація №2

Наступне невикреслене число, 5 — просте. Пройдемо по списку, отриманому в результаті другого проходу, закреслюючи всі числа, кратні 5, тобто, кожне п'яте, починаючи з :

Решето Ератосфена — ітерація №3

Наступне невикреслене число — 7. Виходячи з того, що , то робота алгоритму на цьому завершується (всі складені числа вже викреслені). Таким чином, в списку залишилися тільки впорядковані прості числа, менші або рівні 35.

Блок-схема алгоритму знаходження простих чисел використовуючи решето Ератосфена: