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

Решето Аткіна — швидкий та компактний алгоритм пошуку всіх простих чисел до заданого цілого числа N.
Алгоритм розробили Аткін (англ. A. O. L. Atkin) і Бернштейн (D. J. Bernstein) 1999 року[1][2]. Опубліковано його було у 2003—2004 роках[3].
Асимптотична швидкість алгоритму — — відповідає швидкості найкращих раніше відомих алгоритмів просіювання, але в порівнянні з ними решето Аткіна компактніше (потребує менше пам'яті) — [4].

Див. також

Джерела
  1. A. O. L. Atkin; D. J. Bernstein (1999). Prime sieves using binary quadratic forms. (англ.)
  2. D. J. Bernstein (1999). primegen.
  3. A. O. L. Atkin. Prime sieves using binary quadratic forms // Math. Comp.. — 2004. — Т. 73. — С. 1023—1030.(англ.)
  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.»
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.