Сито Ератосфеня: Знаходження кожного простого числа без повторного ділення

Викреслюйте кратні, зберігайте те, що залишилося

Сітка Ератосфена, розроблена грецьким математиком приблизно в 240 році до нашої ери, знаходить усі прості числа до межі N без перевірки подільності на будь-яке окреме число по черзі. Замість цього вона записує кожне ціле число від 2 до N, а потім повторно бере найменше не викреслене число та викреслює всі його кратні. Все, що залишається після всього процесу — ніколи не викресленого — є простим, за конструкцією: складене число завжди має найменший простий множник, і цей множник гарантовано виловив його.

для p від 2 до N: якщо p не позначено: # p вижило після кожного попереднього процесу → просте для кратних m = p*p, p*p+p, p*p+2p, ... ≤ N: позначте m як складене # все, що не позначено, є простим Єдимій оптимізація, яка має значення, — це початок кожного процесу з p² замість 2p. Будь-яке складене число менше ніж p², яке є кратним p, також повинно бути кратним простішому числу, меншому за p, тому воно вже було викреслене попереднім процесом — початок з p² пропускає непотрібну роботу без втрати нічого.

for p from 2 to N:
    if p is not marked:            # p survived every earlier sweep → prime
        for multiple m = p*p, p*p+p, p*p+2p, ... ≤ N:
            mark m as composite
# everything unmarked is prime

Чому воно зупиняється біля √N

Вам потрібно лише промахуватися з простими до √N. Будь-яке складене число m ≤ N має принаймні один множник ≤ √m ≤ √N, тому якщо m вижило від кожного промаху простих чисел до √N, воно не може бути складним — воно повинно бути простим. Цей єдиний факт перетворює сканування O(N) «простих чисел для перевірки» на O(√N), і це вся причина, чому сито швидке: для N = 10 000 вам потрібно лише промахуватися з 25 простими числами до 100.

Складність: краще ніж тестувати кожне число окремо

Роздільний поділ на всі числа до N коштує приблизно O(N√N). Сітка замість цього витрачає приблизно O(N log log N) роботи — для кожного простого числа p до √N вона позначає близько N/p множини, і сума 1/2 + 1/3 + 1/5 + 1/7 + ... над простими числами збігається (дуже повільно) до log log N за теоремою Мертенса другого виду. На практиці це означає, що сітка знаходить усі прості числа нижче десяти мільйонів за секунду, що неможливо для роздільного поділу настільки швидко.

work ≈ N · ( sum of 1/p for primes p ≤ √N )
        ≈ N · log(log(√N))
        =  O(N log log N)

Основні проміжки та функція підрахунку π(x)

Після того, як сито було запущено, стає легше досліджувати ці питання візуально. π(x), функція підрахунку простих чисел, просто рахує кількість простих чисел, які менші або рівні x — читаючи це безпосередньо з клітинок, що залишилися на ситі. Теорема про розподіл простих чисел стверджує, що π(x) приблизно дорівнює x / ln(x) для великих x, тобто середнє відстань між простими числами поблизу x становить приблизно ln(x) — все більш розріджене навіть тоді, коли їх безліч (факт, який Евклід довів суперечністю більше двох тисяч років тому). Проміжки між простими числами — це відстань між послідовними простими числами — те, що сито робить візуально очевидним: короткі поблизу початку (2, 3, 5, 7 щільно розташовані), розтягуються в середньому, але без відомої найбільшої проміжності та з рідкісними драматичними відхиленнями.

Фактор обертання: швидке ситовання ще швидше

Простий подальший пришвидшувач полягає у повному пропуску парних чисел — після 2 жодне парне число не є простим, тому сито може виділити пам’ять лише для непарних чисел і вдвічі зменшити як пам'ять, так і роботу. Розширення тієї самої ідеї для пропуску кратних 2, 3 та 5 («колесо» з періодом 30) видаляє приблизно 73% компонентів до того, як основне сито навіть починається, за незначний додатковий складний схему індексування. Розділене ситовання — обробка N блоками, які поміщаються в кеш — є іншим стандартним продуктовим трюком, дозволяючи алгоритму масштабуватися до мільярдів без вичерпання пам’яті.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Prime Sieve і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.