Решето Ератосфена

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Метод[ред.ред. код]

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N2 -1. Потім в цьому ряду викреслюються всі числа, які діляться на 2,3, 4 і так далі до N. Числа, які залишилися невикресленими після цієї процедури - прості.

Приклад для n = 20[ред.ред. код]

Запишемо натуральні числа від 2 до 20 в рядок:

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з 2^2=4):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Наступне невикреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з 3^2=9):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Наступне невикреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з 5^2=25). І т. д.

Необхідно викреслити кратні для всіх простих чисел p, для яких p^2\le n. В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для n = 20 вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Алгоритм решета Ератосфена у вигляді програми на псевдокоді для пошуку простих чисел менших
1 000 000
[ред.ред. код]

limit = 1000000
// присвоєння змінній типу стрічка символів sieve$  стрічки, яка складається  з 1000000 літер "Р",
//тобто початково вважаємо, що всі числа прості
sieve$ = string of the character "P" with length limit

// присвоєня змінній prime значення 2 – перше просте число
prime = 2
// цикл (повторення) з перевіркою prime2 < limit
repeat while prime2 < limit 

// зміна літер "Р", порядковий номер (індекс) яких кратний prime (за виключенням індекса prime), на "N"
   set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N"
// змінній prime присвоюється індекс наступної "Р" в стрічці sieve$
    prime = index of the next instance of "P" in sieve$ after index prime
end repeat


Алгоритм (ілюструється анімованим зображенням)[ред.ред. код]

Sieve of Eratosthenes animation.gif
  1. Зробимо список чисел від 2 до найбільшого, про яке хочемо дізнатися чи є простим (дивіться також Тест простоти). Назвемо його Список А. (Це таблиця в лівій частині зображення.)
  2. Запишемо число 2, перше просте число, в інший список для знайдених простих чисел. Назвемо його Список В. (Це список в правій частині зображення.)
  3. Викреслимо 2 і всі кратні 2 числа зі Списку А.
  4. Перше (найменше) невикреслене число в Списку А є простим. Запишемо його в Список В.
  5. Викреслимо це число і всі кратні йому числа зі Списку А. Викреслювання кратних можна почати з числа, яке є квадратом поточного простого числа, бо менші кратні були викреслені на попередньому кроці (наприклад, 6 було викреслене як 2*3 і викреслювати його як 3*2 вже не треба, тобто починаємо з 3*3=32).
  6. Повторюємо кроки 4 і 5 до тих пір, поки в Списку А не залишиться чисел.


Останній кадр попереднього анімованого зображення (прості числа в Списку В записані в продовженні відповідного рядка десятків Списку А - проти «своїх» десятків)

Аналізуючи останнє (неанімоване) зображення можна зробити цікаві спостереження…