# Thread: Optimising this simple piece of code (30 lines)

1. Member Join Date
Jan 2012
Location
Posts
17
Rep Power
0

## Optimising this simple piece of code (30 lines)

For Project Euler :)
This fairly simple piece of code works great, around 600ms to calculate the sum of all primes below 2 million:

Java Code:
```public class projectEuler {

public static void main (String [] args) {

double startTime = System.nanoTime();

int testNum = 1;
long count = 0;
while(testNum < 2000000){
testNum++;
if(primeTest(testNum)){
count += testNum;
}
}
System.out.println(count);
System.out.println(((double)System.nanoTime() - startTime) / 1000000000);

}

public static boolean primeTest(int n) {

if (n == 2 || n == 3)
return true;
if (n < 2 || n % 2 == 0)
return false;

int sn = (int) Math.round(Math.sqrt(n) + 1);
for (int a = 3; a <= sn; a += 2)
if (n % a == 0)
return false;

return true;
}
}```
Others have been getting really, really fast times (easily under 100ms). Could someone please help optimise this code with me?
Thanks.  Reply With Quote

2. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,717
Rep Power
17

## Re: Optimising this simple piece of code (30 lines)

Java Code:
```if (n == 2 || n == 3)
return true;
if (n < 2 || n % 2 == 0)
return false;```
This code can be removed - just don't call the method with small or even n. (In those cases you know what is going to be returned.)

-----

Java Code:
`for (int a = 3; a <= sn; a += 2)`
This code checks all of the odd numbers from 3 for a factor. Those numbers are:

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...

This is a bit wasteful since 1/3 of the trial factors are themselves multiples of 3 and you have already ruled out 3 as a factor. Think about how you might check 5 and 7 and then jump to 11, check 11 and 13 and then jump to 17, etc.  Reply With Quote

3. Member Join Date
Jan 2012
Location
Posts
17
Rep Power
0

## Re: Optimising this simple piece of code (30 lines)

ok, cheers mate.

I'll have to implement some of that.  Reply With Quote

4. ## Re: Optimising this simple piece of code (30 lines) Originally Posted by pbrockway2 This code can be removed - just don't call the method with small or even n. (In those cases you know what is going to be returned.)
That code is a nice atttempt to protect the real body of the method against trivial cases; a better attempt is:

Java Code:
```if (n < 2) return false;
if (n <= 3) return true;
if (n%2 == 0 || n%3 == 0) return false;```
The next part of the code only has to check if n is of the form 6*p+-1 (the other values are most certainly not prime).

kind regards,

Jos
Last edited by JosAH; 01-29-2012 at 08:47 AM.  Reply With Quote

#### Posting Permissions

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