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

- Michael P. (37/37) Mar 31 2009 Hey, I've started to do some of the problems on Project Euler to practic...
- Jarrett Billingsley (8/45) Mar 31 2009 my programming skills. I'm doing #10 right now, and I think I've got a ...
- bearophile (28/29) Mar 31 2009 This will not give you much practice in programming, but if you need pri...
- Robert Fraser (3/8) Apr 01 2009 Yeah that's shorter (vertically; it's almost as long in characters), but...
- Daniel Keep (3/12) Apr 01 2009 None. It's a straightforward stream operation.
- bearophile (8/9) Apr 01 2009 This is simpler and faster (runs in 2.19 seconds), and gives the same re...
- Spacen Jasset (5/46) Apr 01 2009 One thing that may help a little is that you need only loop from 2 to
- Michael P. (4/51) Apr 01 2009 That helped. Ran in about 10-15sec I think after doing that.
- Don (3/55) Apr 01 2009 In isPrime, only test odd divisors (int i=3; i+=2). You already know
- Tiago Carvalho (9/64) Apr 01 2009 I've done this a while ago. But if I remember correctly you only need to...
- Stewart Gordon (7/16) Apr 04 2009 See my reply to Michael. My fast prime finder keeps an array of primes,...
- Stewart Gordon (11/19) Apr 04 2009 You have a serious bug here. Can you see what it is?

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

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

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

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

Robert Fraser wrote:bearophile wrote:None. It's a straightforward stream operation. -- Danielimport 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

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

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

Spacen Jasset Wrote:Michael P. wrote:That helped. Ran in about 10-15sec I think after doing that. Thanks for the help everyone. -Michael P.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

Michael P. wrote:Spacen Jasset Wrote:In isPrime, only test odd divisors (int i=3; i+=2). You already know it's not even.Michael P. wrote:That helped. Ran in about 10-15sec I think after doing that. Thanks for the help everyone. -Michael P.

Apr 01 2009

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

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

Michael P. wrote: <snip>You have a serious bug here. Can you see what it is? <snip>int sum = 2;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.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.

Apr 04 2009