ProjectEuler problem 35

[Stewart Gordon]

On 19/05/2012 16:13, maarten van damme wrote:
> A huge optimization could be made by storing and int array of already
> found primes and test all primes smaller then half the to-test number.
> this will speed up a lot.

Do you mean build an array of already-found primes and use them to test new primes?  You 
need only to try dividing by each prime up to the square root of the number being tested.

> Another huge improvement could be made with hardcoding everything up
> to the prime 3 and then iterate with intervals of 2 instead of 1.

Yes, that's a common optimisation.  Faster still would be to test 6k-1 and 6k+1 for each 
positive integer k.  Indeed, I've done more than this in my time: hard-coded all the 
primes up to 30 and the residues modulo 30 that can possibly be of primes above 30.

Stewart.