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.

On Tue, Mar 31, 2009 at 9:11 PM, Michael P. <baseball.mjp@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.

Michael P. Wrote:

> 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.

This will not give you much practice in programming, but if you need primes quickly you may use my xprimes:
http://www.fantascienza.net/leonardo/so/dlibs/primes.html
The code is here, but the basic routine isn't mine, I have just translated it to D:
http://www.fantascienza.net/leonardo/so/libs_d.zip
You will never find faster D code to generate primes. Yet, there are ways to make that D code twice faster (mostly pulling out out of an opApply, but then you can't use the nice foreach syntax).

The following code runs in 2.37 s on a Core 2 at 2 GHz:

import d.primes, d.string;
void main() {
    long tot;
    foreach (p; xprimes(1_000_000_000))
        if (p < 1_000_000_000)
            tot += p;
        else
            break;

    putr(tot);
}

The correct result:
24739512092254535

(With N= 2 millions it takes "nothing", I am not able to time it).

Shorter version, that runs in about 2.8 seconds:

import d.func, d.primes, d.string;
void main() {
    const int N = 1_000_000_000;
    putr( sum(xtakeWhile((int i){ return i < N;}, xprimes(N))) );
}

Bye,
bearophile

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.

bearophile wrote:
> import d.func, d.primes, d.string;
> void main() {
>     const int N = 1_000_000_000;
>     putr( sum(xtakeWhile((int i){ return i < N;}, xprimes(N))) );
> }

Yeah that's shorter (vertically; it's almost as long in characters), but how much lisp do you have to smoke to understand it?

Robert Fraser wrote:
> bearophile wrote:
>> import d.func, d.primes, d.string;
>> void main() {
>>     const int N = 1_000_000_000;
>>     putr( sum(xtakeWhile((int i){ return i < N;}, xprimes(N))) );
>> }
> 
> Yeah that's shorter (vertically; it's almost as long in characters), but how much lisp do you have to smoke to understand it?

None.  It's a straightforward stream operation.

  -- Daniel

Robert Fraser Wrote:
> Yeah that's shorter (vertically; it's almost as long in characters),

This is simpler and faster (runs in 2.19 seconds), and gives the same result, xtakeWhile isn't required because xprimes already stops nicely when the given max N is reached:

import d.func, d.primes, d.string;
void main() {
    putr( sum(xprimes(1_000_000_000)) );
}

Bye,
bearophile

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.

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.

"Michael P." <baseball.mjp@gmail.com> wrote in message news:gqvksi$1ro$1@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.