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