Решето Ератосфена, наукові парадокси wiki, fandom powered by wikia
Решето Ератосфена - алгоритм знаходження всіх простих чисел до деякого цілого числа, який приписують давньогрецькому математику Ератосфену Киренського.
алгоритм Правити
Для знаходження всіх простих чисел не більше заданого числа n. дотримуючись методу Ератосфена, потрібно виконати наступні кроки:
- Виписати підряд всі цілі числа від двох до n (2, 3, 4, ..., n).
- Нехай змінна p спочатку дорівнює двом - першому простому числу.
- Викреслити зі списку всі числа від 2p до n. діляться на p (тобто, числа 2p. 3p. 4p. ...)
- Знайти Перший не викреслене число, більше ніж p. і привласнити значенням змінної p це число.
- Повторювати кроки 3 і 4 до тих пір, поки p не стане більше, ніж n
- Все не викреслені числа в списку - прості числа.
На практиці, алгоритм можна трохи поліпшити в такий спосіб. На кроці №3, числа можна викреслювати, починаючи відразу з числа, тому що всі складові числа менше його вже будуть викреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли стане більше, ніж.