4 ms·
Another Scoop by Dijkstra?
- ars 15y agoConceptually what this does is instead of laying out a Sieve that is the full size of the largest prime you are generating, you only store a Sieve that has a size of the square root of the largest prime. Then you sort of "carry the Sieve along with you" as you work your way through the numbers. Modifying it always to keep track of the numbers near the current number you are checking. So it still uses a lot more memory than division, but much less than a full Sieve.