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