Решето Аткіна швидкий та компактний алгоритм пошуку всіх простих чисел до заданого цілого числа N Алгоритм розробили Атк

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

Див. також

Джерела

A. O. L. Atkin; D. J. Bernstein (1999). Prime sieves using binary quadratic forms (PDF). (англ.)
D. J. Bernstein (1999). primegen.
A. O. L. Atkin. Prime sieves using binary quadratic forms // Math. Comp.. — 2004. — Т. 73. — С. 1023—1030.(англ.)
Sorenson, Jonathan P. (2015). Two Compact Incremental Prime Sieves. LMS Journal of Computation and Mathematics. с. 675-683. doi:10.1112/S1461157015000194. The fastest known algorithms, including Pritchard’s wheel sieve [16] and the Atkin-Bernstein sieve [1], can do this using at most O(n / log log n) arithmetic operations.
Atkin and Bernstein [1] gave the first compact sieve that runs in sublinear time. {{}}: Cite має пустий невідомий параметр: |1= ()

[paper-1] A. O. L. Atkin; D. J. Bernstein (1999). Prime sieves using binary quadratic forms (PDF). (англ.)

[primegen-2] D. J. Bernstein (1999). primegen.

[quadratic-3] A. O. L. Atkin. Prime sieves using binary quadratic forms // Math. Comp.. — 2004. — Т. 73. — С. 1023—1030.(англ.)

[facsch_papers/968-4] Sorenson, Jonathan P. (2015). Two Compact Incremental Prime Sieves. LMS Journal of Computation and Mathematics. с. 675-683. doi:10.1112/S1461157015000194. The fastest known algorithms, including Pritchard’s wheel sieve [16] and the Atkin-Bernstein sieve [1], can do this using at most O(n / log log n) arithmetic operations.
Atkin and Bernstein [1] gave the first compact sieve that runs in sublinear time. {{}}: Cite має пустий невідомий параметр: |1= ()