project euler #10: optimization with primes
Jarrett Billingsley
jarrett.billingsley at gmail.com
Tue Mar 31 19:23:19 PDT 2009
On Tue, Mar 31, 2009 at 9:11 PM, Michael P. <baseball.mjp at gmail.com> 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.
Look up the Sieve of Eratosthenes. All you have to do then is
generate the primes below 2,000,000, then loop through and sum them
up.
More information about the Digitalmars-d-learn
mailing list