Решето Аткіна
Матеріал з Вікіпедії — вільної енциклопедії.
Решето Аткіна — швидкий та компактний алгоритм пошуку всіх простих чисел до заданого цілого числа N.
Алгоритм розробили Аткін (англ. A. O. L. Atkin) і Бернштейн (D. J. Bernstein) 1999 року[1][2]. Опубліковано його було у 2003—2004 роках[3].
Асимптотична швидкість алгоритму — — відповідає швидкості найкращих раніше відомих алгоритмів просіювання, але в порівнянні з ними решето Аткіна компактніше (потребує менше пам'яті) — [4].
- ↑ 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 web)): Cite має пустий невідомий параметр:|1=(довідка)
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
