[bigpooch]

This is interesting, but does use the knowledge about the
exact number of primes <2.29 x 10^9, although it's quite
easy to compute.

Without having to compute this (perhaps you simply want to
fit as many primes in the CD but don't know EXACTLY how much
space you have), you could consider those positive integers
that are relatively prime to (2x3x5x7x11x13) = 30030. For
every consecutive 30030 numbers, only 5760 are comprime or
a ratio of 576/3003 = 192/1001, so for 440 million bits,
the primes up to about 440 million x 1001/192 or about
2 292 958 000 can be essentially stored on the CD.

OTOH, if there is an upper bound for which primes need to
be found, computing the exact number of primes helps reduce
the amount of space significantly.