www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - project euler #10: optimization with primes

reply Michael P. <baseball.mjp gmail.com> writes:
Hey, I've started to do some of the problems on Project Euler to practice my

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.
Mar 31 2009
next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
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=



king solution. It's just that it's way too slow.

 Here's the link:
 http://projecteuler.net/index.php?section=3Dproblems&id=3D10
 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 mo=


st 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()
 {
 =A0 =A0 =A0 =A0int sum =3D 2;
 =A0 =A0 =A0 =A0long bigNum =3D 10; //Or 2 million
 =A0 =A0 =A0 =A0for ( int i =3D 3; i < bigNum; i +=3D 2 )
 =A0 =A0 =A0 =A0{
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if( isPrime( i ) )
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0{
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0sum +=3D i;
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0}
 =A0 =A0 =A0 =A0}
 =A0 =A0 =A0 =A0writefln( sum );
 =A0 =A0 =A0 =A0return 0;
 }

 //Functions
 bool isPrime( long n )
 {
 =A0 =A0 =A0 =A0for( int i =3D 2; i < n; i++ )
 =A0 =A0 =A0 =A0{
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if ( n % i =3D=3D 0 )
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0{
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0return false;
 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0}
 =A0 =A0 =A0 =A0}
 =A0 =A0 =A0 =A0return 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.
Mar 31 2009
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Mar 31 2009
parent reply Robert Fraser <fraserofthenight gmail.com> writes:
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?
Apr 01 2009
next sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
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
Apr 01 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Apr 01 2009
prev sibling parent reply Spacen Jasset <spacenjasset yahoo.co.uk> writes:
Michael P. wrote:

 Hey, I've started to do some of the problems on Project Euler to practice my

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.
Apr 01 2009
parent reply Michael P. <baseball.mjp gmail.com> writes:
Spacen Jasset Wrote:


 Michael P. wrote:

 Hey, I've started to do some of the problems on Project Euler to practice my

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.
Apr 01 2009
next sibling parent Don <nospam nospam.com> writes:
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

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.
Apr 01 2009
prev sibling next sibling parent reply "Tiago Carvalho" <merlin3000 c-core.org> writes:
"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 

 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.
Apr 01 2009
parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Tiago Carvalho wrote:
<snip>

 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.


See my reply to Michael.  My fast prime finder keeps an array of primes, 
and maintains a slice of this array up to the square root of the number 
being tested.


 If a umber can't 
 be divided by none of the primes below it, it's prime.


No, if it can't be divided by _any_ of the primes below it, it's prime.

Stewart.
Apr 04 2009
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Michael P. wrote:
<snip>

     int sum = 2;






You have a serious bug here.  Can you see what it is?

<snip>

 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. 


I've optimised your version to compare against a pre-calculated sqrt(n), 
and check only against 6k-1 and 6k+1 (in both loops).  On my Windows 
Vista box with a 2.4GHz CPU, it takes just under 6 seconds to add the 
primes up to 10 million.

That said, the other day I wrote an even faster prime finder, which 
takes just over 2.5 seconds to do the same.

Stewart.
Apr 04 2009