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

Решето Ератосфена - алгоритм знаходження всіх простих чисел до деякого цілого числа Шаблон: Math. який приписують давньогрецькому математику Ератосфену Киренського [1]. Як і в багатьох випадках, тут назву алгоритму говорить про принцип його роботи, тобто решето на увазі фільтрацію. в даному випадку фільтрацію всіх чисел за винятком простих. У міру проходження списку потрібні числа залишаються, а непотрібні (вони називаються складовими) виключаються.

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

Для знаходження всіх простих чисел не більше заданого числа n. дотримуючись методу Ератосфена, потрібно виконати наступні кроки:

1. Виписати підряд всі цілі числа від двох до n (2, 3, 4, ..., n).
2. Нехай змінна p спочатку дорівнює двом - першому простому числу.
3. Закреслити в списку числа від 2p до n вважаючи кроками по p (це будуть числа кратні p. 2p. 3p. 4p. ...).
4. Знайти перше незачёркнутое число у списку, більше ніж p. і привласнити значенням змінної p це число.
5. Повторювати кроки 3 і 4, поки можливо.

Тепер все незачёркнутие числа в списку - це все прості числа від 2 до n.

На практиці, алгоритм можна поліпшити в такий спосіб. На кроці № 3 числа можна закреслювати починаючи відразу з числа p 2. тому що всі складові числа менше нього вже будуть закреслені до цього часу. І, відповідно, зупиняти алгоритм можна, коли p 2 стане більше, ніж n. [2] Також, всі прості числа (крім 2) - непарні числа, і тому для них можна вважати кроками по 2p. починаючи з p 2.

складність алгоритму

Складність алгоритму становить $O\; (n\; \backslash \; log\; (\backslash \; log\; n))$ операцій при складанні таблиці простих чисел до $n$ [3].

доказ складності

при обраному $n\; \backslash \; in\; \backslash \; mathbb$ для кожного простого $p\; \backslash \; in\; \backslash \; mathbb$

\ Colon p \ le n буде виконуватися внутрішній цикл, який зробить $\backslash \; frac$

дій. Отже, потрібно оцінити наступну величину:

Так як кількість простих чисел. менших або рівних $n$, оцінюється як $\backslash \; frac$, і як наслідок, $k$-е просте число приблизно дорівнює $k\; \backslash \; ln\; k$, то суму можна перетворити:

Тут з суми виділено доданок для першого простого числа, щоб уникнути поділу на нуль. Тепер слід оцінити цю суму інтегралом:

У підсумку виходить для початкової суми:

$\backslash \; Sum\; \backslash \; limits\_\; \backslash \; colon\; p\; \backslash \; le\; n>$

> \ Approx n \ ln \ ln n + o (n)

Більш суворе доказ (і дає більш точну оцінку з точністю до константних множників) можна знайти в книзі Hardy і Wright «An Introduction to the Theory of Numbers» [4].

Оптимізована реалізація (що починається з квадратів) на псевдокоді [5] [6].

Приклад для n = 30

Запишемо натуральні числа починаючи від Шаблон: Math до Шаблон: Math в ряд:

Перше число в списку, Шаблон: Math - просте. Пройдемо по ряду чисел, закреслюючи все числа кратні Шаблон: Math (тобто кожне друге, починаючи з Шаблон: Math):

Наступне незачеркнутое число, Шаблон: Math - просте. Пройдемо по ряду чисел, закреслюючи все числа кратні Шаблон: Math (тобто кожен третій, починаючи з Шаблон: Math):

Наступне незачеркнутое число, Шаблон: Math - просте. Пройдемо по ряду чисел, закреслюючи все числа кратні 5 (тобто кожна п'ята, починаючи з Шаблон: Math). І т.д.

Наступне незачеркнутое число - Шаблон: Math. Його квадрат, Шаблон: Math - більше Шаблон: Math-ти, тому на цьому робота завершена. Всі складові числа вже закреслені:

модифікації методу

Необмежений, поступовий варіант

У цьому варіанті прості числа обчислюються послідовно, без обмеження зверху, як числа що знаходяться в проміжках між складовими числами, які обчислюються для кожного простого числа Шаблон: Math. починаючи з його квадрата, з кроком в Шаблон: Math (або для непарних простих чисел Шаблон: Math) [2]. Може бути представлений символічно в парадигмі потоків даних як

перебір дільників

Решето Ератосфена часто плутають з алгоритмами, які фільтрують з заданого інтервалу складені числа. тестуючи кожне з чисел-кандидатів за допомогою перебору дільників. [7]

Широко відомий функціональний код Девіда Тернера 1975 года [8] часто приймають за решето Ератосфена, [7] але насправді це далекий від оптимального варіант з перебором подільників.

решето Ейлера

Решето Ейлера Шаблон: Ні АІ це варіант решета Ератосфена, в якому кожне складене число видаляється зі списку тільки один раз.

Складається вихідний список починаючи з числа Шаблон: Math. На кожному етапі алгоритму перший номер в списку береться як наступне просте число, і визначаються його твори на кожне число у списку які маркуються для последуюшіе видалення. Після цього зі списку прибирають перше число і все помічені числа, і процес повторюється знову:

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

Решето тільки по непарних числах

Оскільки всі парні числа. крім 2, - складові, то можна взагалі не обробляти ніяк парні числа, а оперувати тільки непарними числами. По-перше, це дозволить вдвічі скоротити обсяг необхідної пам'яті. По-друге, це зменшить кількість виконуваних алгоритмом операцій (приблизно вдвічі).

Це можна узагальнити на числа взаємно прості не тільки з 2 (тобто непарні числа), але і з 3, 5, і т. Д.

Зменшення обсягу споживаної пам'яті

Алгоритм Ератосфена фактично оперує з $n$ битами пам'яті. Отже, можна істотно заощадити споживання пам'яті, зберігаючи $n$ змінних булевского типу не як $n$ байт. а як $n$ біт, тобто $n\; /\; 8$ байт пам'яті.

Такий підхід - «бітове стиснення» - ускладнює оперування цими бітами. Будь-яке читання або запис біта будуть являти собою кілька арифметичних операцій. Але з іншого боку істотно поліпшується компактність в пам'яті. Великі інтервали вміщаються в кеш-пам'ять яка працює набагато швидше звичайної так що при роботі по-сегментно загальна швидкість збільшується.

Решето Ератосфена з лінійним часом роботи

Цей алгоритм виявляє для кожного числа Шаблон: Math в відрізку Шаблон: Math його мінімальний простий дільник Шаблон: Math.

Також підтримується список всіх простих чисел - масив Шаблон: Math. спочатку порожній. В ході роботи алгоритму цей масив буде поступово заповнюватися.

Спочатку все величини Шаблон: Math заповнимо нулями.

Далі слід перебрати поточне число Шаблон: Math від Шаблон: Math до Шаблон: Math. Тут може бути два випадки:

• Шаблон: Math. це означає, що число Шаблон: Math - просте, так як для нього так і не знайшлося інших дільників.

• Шаблон: Math. це означає, що поточне число Шаблон: Math - складене, і його мінімальним простим дільником є ​​Шаблон: Math.

В обох випадках далі починається процес розстановки значень в масиві Шаблон: Math. слід брати числа, кратні Шаблон: Math. і оновлювати у них значення Шаблон: Math. Однак основна мета - навчитися робити це таким чином, щоб в результаті у кожного числа значення Шаблон: Math було б встановлено не більше одного разу.

Стверджується, що для цього можна поступити таким чином. Розглядаються числа виду Шаблон: Math. де Шаблон: Math послідовно одно всім простим числам що не перевищують Шаблон: Math (якраз для цього знадобилося зберігати список всіх простих чисел).

У всіх чисел такого виду проставимо нове значення Шаблон: Math - воно має дорівнювати Шаблон: Math [9].

Примітки

література