I got the impression that it was based on prime numbers, but not exactly. The first few are easy to figure out: 2, 3, 5, 7...then it gets harder....11, 13, 17. 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
$