3 ms·
The Sieve of Atkin is VERY fast at generating primes between 1 and n. It asymptotically speeds up the process of generating prime numbers. It has time complexi
by ChrisCinelli 3y ago
The Sieve of Atkin is VERY fast at generating primes between 1 and n.
It asymptotically speeds up the process of generating prime numbers. It has time complexity O(n/(log log n))
https://www.baeldung.com/cs/prime-number-algorithms https://www.baeldung.com/cs/prime-number-algorithms
- anonymoushn 3y agoYour link seems to say it has time complexity O(n)?
- hgsgm 3y agoIf you count everything carefully, it's O(n / log log n) https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-... They are essentially the same in all conceivable practical cases in this Universe. log log (atoms in universe) < 100
- anonymoushn 3y agoThis seems to be a matter of the above source reporting a variation of the algorithm that is asymptotically slower than the algorithm given in the paper *and* uses asymptotically more memory. Thanks for posting the paper!