you might need to add timing info how long it takes to find all the primes. If you have ideas to improve the algorithm you can measure it.

The ideas of Fletcher are good ones. you should try to implement them;

If those work you can make even a faster primefinder.

recall 2x3x5 = 30

=> if we look at blocks of 30 numbers and filter all multiples of 2,3,and 5 we have this row [30-60]

31 37 41 43 47 49 53 59 (8 values)

or written otherwise

30 +1 +7 +11 +13 +17 +19 +23 +29

so if you have a loop that makes steps of 30, you only need to check these 8 offsets as the others are divisable by 2,3, or 5.

checking 8 in 30 = 26.7% of the values, that is almost a factor 2 faster than only checking the odd numbers, which is allready a factor 2 faster than checking all numbers..

The nice part of this trick is that you can encode the set of eight possible primes into one byte. imagine an array in which the arrayindex indicates the numberx30 and every bit indicates one of the eight mentioned offsets. a 1 bit means prime, a 0 bit means no prime. The values 1..60 will give these two bytes:

01111111 11111011 // the first 0 = byte 0 x 30 + offset 1 = 1, the second 0 is byte 1 x 30 + offset 19 = 49

Note the numbers 2,3,5 are not encoded in these bytes.

This way an array of 1000 bytes can hold (encoded) all the primes from 1 - 30.000 !!

*Although this trick can be expanded to larger jumps, the number of offsets will increase and the speed improvement is getting less. *