project euler #10: optimization with primes
Stewart Gordon
smjg_1998 at yahoo.com
Sat Apr 4 12:20:55 PDT 2009
Michael P. wrote:
<snip>
>>> int sum = 2;
You have a serious bug here. Can you see what it is?
<snip>
>> One thing that may help a little is that you need only loop from 2 to
>> sqrt(n) in the isPrime function, otherwise you end up testing for
>> factors > sqrt(n) twice. A factor over sqrt(n) must have a
>> corresponding factor less than sqrt(n) for a given n.
>
> That helped. Ran in about 10-15sec I think after doing that.
> Thanks for the help everyone.
I've optimised your version to compare against a pre-calculated sqrt(n),
and check only against 6k-1 and 6k+1 (in both loops). On my Windows
Vista box with a 2.4GHz CPU, it takes just under 6 seconds to add the
primes up to 10 million.
That said, the other day I wrote an even faster prime finder, which
takes just over 2.5 seconds to do the same.
Stewart.
More information about the Digitalmars-d-learn
mailing list