Решето Аткіна

Решето Аткіна — швидкий та компактний алгоритм пошуку всіх простих чисел до заданого цілого числа N.
Алгоритм розробили Аткін (Шаблон:Lang-en) і Бернштейн (Шаблон:Lang) 1999 року. Опубліковано його було у 2003—2004 роках.
Асимптотична швидкість алгоритму — $O(\frac{N}{\log \log N})$ — відповідає швидкості найкращих раніше відомих алгоритмів просіювання, але в порівнянні з ними решето Аткіна компактніше (потребує менше пам'яті) — $O(N^{\frac{1}{2}+o(1)})$.

Див. також

• Решето Ератосфена
• Колесна факторизація