project euler #10: optimization with primes
Michael P.
baseball.mjp at gmail.com
Wed Apr 1 04:58:10 PDT 2009
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.
More information about the Digitalmars-d-learn
mailing list