[pzhon]

[ QUOTE ]
[ QUOTE ]
there is an equation n/ln(n) which will estimate the number of primes less than n, so the answer is 2.29e9/ln(2.29e9) for the approximate number of non primes. i dont know about the storage space stuff but the approx number of primes is 106,255,539

[/ QUOTE ]
That's just an estimate though - a bounding function exists and should be used if we want a rigorous answer (it's on wikipedia if anyone is interested).

[/ QUOTE ]
It's much easier to compute the number of primes than to determine what they are. For example, you can use inclusion-exclusion from a list of primes up to the square root of the number, and it's not hard to produce a list of primes under sqrt(2.29 billion) < 50,000. Once the number is computed, it can be written at the start.

There are 111,720,807 = k primes less than 2,290,000,000= n. n choose k has about 193.86 million digits in decimal, or about 644 million digits in binary. That's a bit too large to fit inside 440 million bits.

So, using that there is only one even prime, the other 111,720,806 are a subset of the 1,145,000,000 odd numbers. The number of such subsets has about 528 million digits in binary. Doing the same for 3 gives a subset of size 111,720,805 out of a set of size roughly n * 1/3. The number of such subsets has about 458 million digits in binary. Taking out the numbers divisible by 5 gives a subset of 111,720,804 of a set of size roughly n * 4/15. The number of such subsets has about 419 million digits in binary, so a particular subset can be expressed as a binary number with under 420 million binary digits.