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
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.
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=
my programming skills. I'm doing #10 right now, and I think I've got a wor= 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
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.
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
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.
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
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.
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 
 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.
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