Hey Bernhard,

 > But at some point the average number of non primes
 > between primes will grow larger than the bits/number
 > (int, long, float) and storing the primes as numbers
 > will consume less space (and maybe time).

    That approach presupposes that your program knows or cares what the numeric
equivalents are of the bits that remain set (and therefore represent prime
numbers).

    All I can say is that that was not what I found, Bernhard. Given
umpteen banks of 64KB ram in an 8-bit bank switched system, and allowing
about 4KB for the program, there is a very large bitfield left. That
bitfield only has to extend to sqrt(last prime). As I said, it was in Z80
assembler and ran on a 2MHz machine in under ten seconds IIRC for the
calculation, but it took endless eons to print the results out on a serial
output device. All this was nearly
a quarter of a century ago. I doubt whether I can find the program. It was a
highly modified sieve of Eratosthenes, with every optimization possible on a
Z80 with the Cromemco Z80 Macro Assembler. :-)

 > ... But examining the first million prime numbers
 > showed that there are an average of 15 numbers between
 > 2 prime numbers and growing _very_ slowly (logarithmic
 > or such). So a bitfield will consume less memory
 > unless someone has a real incredible amount of memory.
 > As the number of bits/number is growing
 > logarithmically, a bitfield may well be the way with
 > the lowest memory demands at all.

    I wasn't concerned with how many numbers came between, Bernhard. It's a
fundamentally different approach - brute force and ignorance. :-) When you are
just resetting bits, it really doesn't matter where they are as long as they
are within the addressable memory space. All that matters is how quickly you
can calculate which bit you must address or ignore because it is already
reset. :-) There is also no virtue in repeating calculations indefintely,
or in going over again what you have already established, so it limited
itself to calculating sqrt(max) once, and using the integer result +1 for
comparisons as a constant, then resetting multiples of primes already found
- i.e. for all positive integers, if the bit representing me is set, reset
all my multiples larger than me and not excluded by a previous iteration up
to limit of const representing sqrt(max). This sieve was binary logic at
its most basic level - either a number is prime or it is not - a 1 or a 0.

    To put it simply 1 & 2 are starting primes, so every second bit is
reset, then every odd third bit that is still a 1, then every fifth odd bit
beyond 6 that is still a 1, then every 7th bit that is still a 1, then
every 11th bit and so on. It's astonishing how quickly the loops terminate.

Best wishes,
Bill.

---