Quote Originally Posted by Evil_Giraffe View Post
Essentially, I would imagine that you could keep a list of primes plus a multiple of that prime. As you increment the candidate prime, check whether any of the multiples of the prime are equal to the current candidate. If they are, the number is not a prime. Also check whether any of the multiples are less than the prime, if so you add the prime to the multiple again to get the next multiple. This should always be greater than the current candidate.

This approach should be quicker than checking the modulo of the candidate prime because it avoids any division operations, and also only bothers to check for prime factors of the candidate. It looks correct to my brief analysis, but you'd probably want to run a few tests to check.
Interesting, off the top of your head, just how much of an improved performance would you expect ?