# Optimising this simple piece of code (30 lines)

• 01-29-2012, 02:48 AM
hvince95
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:

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.
• 01-29-2012, 03:06 AM
pbrockway2
Re: Optimising this simple piece of code (30 lines)
Quote:

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.)

-----

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.
• 01-29-2012, 08:14 AM
hvince95
Re: Optimising this simple piece of code (30 lines)
ok, cheers mate.

I'll have to implement some of that.
• 01-29-2012, 09:43 AM
JosAH
Re: Optimising this simple piece of code (30 lines)
Quote:

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:

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