"Michael P." <[email protected]> wrote in message
news:[email protected]...
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.
