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

Answer 3

There is the overhead of VM itself to worry about when comparing java runtimes (println can take different periods at every execution for instance). To get a proper comparison of runtimes, run each one a thousand times and get average values for more accurate results.

Also, implementing the Sieve of Erastothenes in Java is not that difficult an will give you very quick results too, though it will use more memory.

Answer 4

If you're interested in the most efficient algorithm known to date whether a given number is prime, you should consider reading about the AKS primality test, which runs in polylogarithmic time.

(This answer basically is a reiteration of another answer to a question regarding primality tests.)

Answer 5

1) did you consider to use Sieve of Eratosthenes for finding primes?

2) you shouldn't really measure efficiency by using running time

3) your if statement in is prime, if you are checking is n = {2,3,5} use it to return result, that will prevent you from executing rest of code (not much time saver in this case)

4) your for loop, you can do it for i from 7 (condition for 5 you already check, and 6 is not prime number) to sqrt(n)

Answer 6

Maybe this article can help you:

boolean isPrime(int n) {
//check if n is a multiple of 2
if (n%2==0) return false;
//if not, then just check the odds
for(int i=3;i*i<=n;i+=2) {
    if(n%i==0)
        return false;
}
return true;
}