project euler #10: optimization with primes

Stewart Gordon smjg_1998 at yahoo.com
Sat Apr 4 12:41:32 PDT 2009


Tiago Carvalho wrote:
<snip>
> I've done this a while ago. But if I remember correctly you only need to 
> verify 2, 3, and after that all primes will be forms of 6k+1 or 6k-1. 
> This made my code a lot faster at the time.
> 
> Don't know if this is faster in this case since you have to store values 
> in an array (or other storage), but if you store the calculated primes, 
> you only need to test the current value against those.

See my reply to Michael.  My fast prime finder keeps an array of primes, 
and maintains a slice of this array up to the square root of the number 
being tested.

> If a umber can't 
> be divided by none of the primes below it, it's prime.

No, if it can't be divided by _any_ of the primes below it, it's prime.

Stewart.


More information about the Digitalmars-d-learn mailing list