project euler #10: optimization with primes

[Don]

Michael P. wrote:
> 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.

In isPrime, only test odd divisors (int i=3; i+=2). You already know 
it's not even.