project euler #10: optimization with primes

[Tiago Carvalho]

"Michael P." <baseball.mjp at gmail.com> wrote in message 
news:gqvksi$1ro$1 at digitalmars.com...
> Spacen Jasset Wrote:
>
>> Michael P. wrote:
>> > Hey, I've started to do some of the problems on Project Euler to 
>> > practice my programming skills. I'm doing #10 right now, and I think 
>> > I've got a working solution. It's just that it's way too slow.
>> > Here's the link:
>> > http://projecteuler.net/index.php?section=problems&id=10
>> > The code works fine with sum of primes below 10. It output 17.
>> > But for 2 million, it takes quite a while, and an FAQ on the page said 
>> > most problems are made with being run within a minute. Mine was gonna 
>> > quite a bit longer.
>> > Here is my code:
>> >
>> > //Import
>> > import std.stdio;
>> > import std.math;
>> >
>> > //Main
>> > int main()
>> > {
>> > int sum = 2;
>> > long bigNum = 10; //Or 2 million
>> > for ( int i = 3; i < bigNum; i += 2 )
>> > {
>> > if( isPrime( i ) )
>> > {
>> > sum += i;
>> > }
>> > }
>> > writefln( sum );
>> > return 0;
>> > }
>> >
>> > //Functions
>> > bool isPrime( long n )
>> > {
>> > for( int i = 2; i < n; i++ )
>> > {
>> > if ( n % i == 0 )
>> > {
>> > return false;
>> > }
>> > }
>> > return true;
>> > }
>> >
>> > I'm pretty sure the isPrime() function can be done better.
>>
>> 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.
> -Michael P.

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. If  a umber can't be 
divided by none of the primes below it, it's prime.