project euler #10: optimization with primes

[Spacen Jasset]

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.