"is prime" algorithm runtime

Question

I'm trying to make the fastest algorithm to find out if a number is prime. I'm doing this for each number from 3 to 100,000.

   for(int i = 3; i < 100000; i += 1)
        if(isPrime(i))
            System.out.println(i);

and it takes 0.52 seconds. My friend suggested to not iterate for even numbers:

for(int i = 3; i < 100000; i += 2)
        if(isPrime(i))
            System.out.println(i);

and it takes 0.53 seconds (probably a random difference).

Why doesn't his suggestion reduce the runtime? if I iterate through less numbers I'd expect that the program will run faster.

Code of isPrime():

public static boolean isPrime(int n)
{
    if((n % 2 == 0 && n != 2) || (n % 3 == 0  && n != 3)|| (n % 5 == 0 && n != 5))
        return false;
    for(int i = 5; i < n / 5; i += 2)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

Answer 1

Most probably the bulk of the time is needed for printing out the primes to the console. Thus reducing the numbers tested won't notably affect the speed of the program, if the number of primes is not reduced as well.

Try to collect the primes into a string and print that out once, like this:

StringBuilder b = new StringBuilder();
for(int i = 3; i < 100000; i += 1)
    if(isPrime(i))
      b.append(i).append("\n");

System.out.println(b.toString());

Answer 2

Apart from algorithmical issues, your bottleneck is most likely writing to the System.out stream. That is a time-consuming task, I think you should leave that part out of the benchmark loop. To quickly test this, just comment it out (with the corresponding if statement):

int iterations=100000;
long time = System.nanoTime();
for(int i = 3; i < 100000; i += 2) { //notice: always use curly brackets!!!
    isPrime(i);
}
long endTime = System.nanoTime();
System.out.println("Time to go through " + iterations + " iterations: " + (endTime>time?endTime-time:endTime+time));
//notice: nanoTime might turn around, resulting in smaller (negative) endTime value

Also, the answer of Thomas is much more detailed regarding the System.out.print issue, and also provides the appropriate approach of concatenating a lot of strings.

Algorithmic problems:

If you are going with a sieve of Erastothenes approach, you already have found all the smaller primes when searching for the next one. So you should store them, and instead of checking each and every odd number >5, you only have tocheck those that you already have.

Also, at the same time, you don't have to check all of them, only those, that are smaller than, or equal to the square root of your number:

//suppose we have a List<Integer> primeList (populated by previous execution loops)
// and Integer numberTested as the number under testing

for(int i=0; i<primeList.size();i++) {
    if(numberTested%primeList.get(i)==0) {
        //divider found, not prime
        break;
    }        

    if(primeList.get(i)>Math.sqrt(numberTested)) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }
}  

What is the problem with this? Math.sqrt is a costly operation. Much costlier than multiplication... So if the range of numbers permits (you have to have that always in mind!), we can use multiplication to get the comparison quicker:

sqrt(a)>b === a*a>b given that both a and b are positive integers.

    Integer currentPrimeSquare = primeList.get(i)*primeList.get(i);
    if(currentPrimeSquare>numberTested) {
        //still not found a divider -- we found a prime
        primeList.add(numberTested);
        break;
    }

To further tune this, you could store the squares of the primes too - given you have enough memory....