alt Hacker NewsThere 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/
Replies
hnlyman • today at 5:25 PM
Yep, this is the natural way to go, especially considering the possibility of parallel computing and the importance of cache locality, etc.
The 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