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.

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.

ok, cheers mate.

I'll have to implement some of that.

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