There is a very beautiful way to do it using much less memory. You need O(sqrt(n)/log(n)) memory, not O(n), if you keep track of the list of primes found so fa

There is a very beautiful way to do it using much less memory. You need O(sqrt(n)/log(n)) memory, not O(n), if you keep track of the list of primes found so far, and a fixed-size interval over which you sieve: [1, k], [k+1, 2k], [2k+1, 3k], ... Now, for the beautiful part, if you skip multiples of 2, 3 and 5, and work in blocks of 2 * 3 * 5 = 30 numbers, you only need to sieve {1, 7, 11, 13, 17, 19, 23, 29} + i*30. 8 booleans, that happen to fit in 1 byte. So 1 byte = 1 interval of 30 numbers. Next, you can unroll the sieving loop, but no compiler will do this for you, you have to do it by hand. This allows you to sieve up to 8 multiples per iteration. I have an implementation of it in Julia here: https://github.com/haampie/FastPrimeSieve.jl https://github.com/haampie/FastPrimeSieve.jl which was influenced by https://github.com/kimwalisch/primesieve https://github.com/kimwalisch/primesieve.