1. Member
Join Date
Apr 2012
Posts
74
Rep Power
0

Speed up program?

I created a program to give me the sum of all prime numbers below 2 million. It works, but it takes a really long time to process. I have tried to fiddle around with it, trying to figure out where I can take out ifs and such, but hasn't made any difference. How can I make it go faster?

Java Code:
```public class Problem10 {
public static void main (String[] args){

int x, y;
long a = 0;

for (x= 2; x <= 2000000; x++)
{
if (x==2000000)
{
System.out.println("The sum of all the primes below two million:" + a);
System.exit(0);
}

y=2;
outerloop:
do
{

if (PrimeN(x, y))
{
break outerloop;
}
y++;
}
while (y<x);

if (x==y)
{
a +=x;

}

}
}

public static boolean PrimeN(int a, int b){

if (a%b==0){
return true;
}

else
{
return false;
}

}

}```
Cheers!

2. Re: Speed up program?

For one, you could cut down on the iterations by using while(y * y < x). think about why that's valid first.

There are probably other optimizations possible.

db
Last edited by DarrylBurke; 04-25-2012 at 12:51 PM.

3. Re: Speed up program?

Remove the PrimeN method. It only does one thing that could be done in-line.

4. Member
Join Date
Apr 2012
Posts
74
Rep Power
0

Re: Speed up program?

Yes, because if y * y = x, x is not a prime number. Thanks, I will try it and see if it speeds up. Ok thanks I will remove the PrimeN method too.

5. Re: Speed up program?

Use a Sieve for finding those prime numbers; a couple of million bits isn't that much and the creation of a Sieve is fast.

kind regards,

Jos

6. Member
Join Date
Apr 2012
Posts
74
Rep Power
0

Re: Speed up program?

Originally Posted by JosAH
Use a Sieve for finding those prime numbers; a couple of million bits isn't that much and the creation of a Sieve is fast.

kind regards,

Jos
Thanks Jos, that looks awesome!

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•