Replies

By the time you get to 2^20 it is very hard.

Not really.

On my Mac, using a simple-minded Python program (an interpreted language), it takes around a second to count the primes up to 2**20:

$ time factor count-primes $((2**20))
     Limit    Count Density
   1048576    82025   7.82%

real	0m0.986s
user	0m0.921s
sys	0m0.036s
$

Here are the last ten of them:

time factor show-primes $((2**20)) 10
[1048391, 1048423, 1048433, 1048447, 1048507, 1048517, 1048549, 1048559, 1048571, 1048573]

real	0m0.755s
user	0m0.694s
sys	0m0.040s
$

Moving up to 2**24, things do slow down:

$ time factor count-primes $((2**24))
     Limit    Count Density
  16777216  1077871   6.42%

real	0m15.389s
user	0m14.747s
sys	0m0.244s
$