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.
