3 ms·
There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For exa
by senfiaj 7mo ago
There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For example, for n = 1000000, the RAM has to store only 168 additional numbers.
I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/ https://surenenfiajyan.github.io/prime-explorer/
- dahart 7mo agoThe Pseudosquares Sieve will drop the memory requirements much further from sqrt(n) to log^2(n). https://link.springer.com/chapter/10.1007/11792086_15 https://link.springer.com/chapter/10.1007/11792086_15
- adgjlsfhk1 7mo agoIMO that algorithm is barely a sieve. It is technically pareto optimal, but it seems like in practice it would just end up worse than either an optimized segmented sieve (it is ~log(n)^2 slower) or an O(1) memory method (probable prime test followed by a deterministic prime test) depending on how large and how wide the numbers you're testing are.
- hnlyman 7mo agoYep, this is the natural way to go, especially considering the possibility of parallel computing and the importance of cache locality, etc.