JH> JB>   to avoid the sqrt() you could if you're working
JH> JB>   sequentially you can store the square of the prime
JH> JB>   above thats too big to be used yet and when you reach
JH> JB>   that number go the the next prime in your list etc...
JH>   The sqrt is not a problem, since it only needs to be done
JH>   once per iteration and today most computers have FPUs,
JH>   right?-)
   You should be able to get 97,000 primes stored in 400K
   pretty easily, even if you have to use an array of pointers
   to 16K arrays of unsigned long integers.
   As to the square root, they proceed sequentially, more or
   less, and you are only interested in the integer value, so
   you could retain the sqrt of the previous number and add
   one until it exceeds the sqrt of the new number. I think
   this is what was meant by the above suggestion, though my
   reading may not be quite clear on it.
   On startup, you would define the limit as, say 3, which you
   would use until your number to be tested exceeded 9, and then
   you would increment to 4 until 16, 5 until 25, etc..
   That takes ALL the FP calculations out, and actually removes
   the sqrt calculation for a large number of the iterations
   altogether, reducing them to a simple comparison.
while(num > square)
{
   root++;
   square = root * root;
}
   This doesn't do much for low numbers, but when you get up
   into higher ranges, where the root is like 250, incrementing
   the root by one takes care of a range of 500 numbers.
   It isn't much, as you say, in light of the FPU almost
   universally in use these days, ( nudge, nudge, wink, wink ),
   but it gives a decent performance boost otherwise.
   If you've got the ability to allocate large sums of memory,
   or can store the primes on a reasonably fast disk, then it
   should be possible to quickly progress to a huge number of
   primes. On a disk, you would likely use fread() to grab
   large blocks of data into an unsigned long array, or some
   sort of huge number array, if you are using a custom type.
   In the following message, or a preceding message if things
   get turned around enroute, (  ), is an implementation of
   just such a scheme, to find all the primes in the range of
   most unsigned long integers, which is pow(2, 32).
   I use two 64,000 byte buffers. One holds the first 16,000
   primes, used for division, and the other is just a buffer
   to hold results, dumping them to disk when full. I let it
   run for about 8 hours on a 486sx25, which is NOT a speed
   demon, compiled under QC2.5, ALSO not a speed demon, and
   was in the range of 25 million with a primes file of over
   two and a half megabytes when I interrupted it, which was
   possible because it was running in the IDE in debug mode.
   A more advanced setup, with very large numbers, perhaps
   implemented by BCD, might be used to reach extremely large
   prime numbers. As it is, it could easily be edited to allow
   continuation and test for a keypress when dumping to disk so
   that one could quit and restart at will.
   The size of the primes divisor array could be increased in
   implementations utilizing non-standard malloc() utilities,
   also, though the square of the 16,000th prime is a rather
   LARGE number as it is! :)
   176,063 is good to about 30 billion. Another 16,000 should
   make it possible to test extremely large numbers, and going
   to 64,000 should make it able to process astoundingly huge
   numbers quite quickly.
   For the average pentium systems of today, allowing that
   there is 1M available, and using 16-byte BCD integers, the
   64,000 prime divisors array is easily possible without
   resorting to disk access along the way. This gives us the
   ability to process primes up to 32 digits in length, which
   is not too shabby, really. I am assuming, of course, that
   the square of the 64,000th prime is larger than the given
   limit of 99,999,999,999,999,999,999,999,999,999,999. 
   One would necessarily have to include limiting conditions
   to keep from exceeding that value, as well as the value
   of the 64,000th prime squared, if that is less.

---
> ] It's around somewhere. I put it where I wouldn't lose it....

---