What is the time complexity of the algorithm to check if a number is prime?

What is the time complexity of the algorithm to check if a number is prime?

This is the algorithm :

bool isPrime (int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i=3; (i*i) <= number; i+=2) {
if (number % i == 0 ) return false;
}
return true;
}
• you loop from 3 to sqrt(number), this is enough info for you to figure out the rest... – ratchet freak May 8 '13 at 7:37
• Also, you only need to divide by the primes you've already calculated (granted this means keeping a list of said primes). e.g. you can skip diving something by 9, if it's divisible by 9 it's also divisible by 3, and you'll already have tried to divide it by 3. – Binary Worrier May 8 '13 at 9:49

O(sqrt(n)) in the magnitude of the number, but only as long as you use int

Note that complexities for prime number related algorithms are often discussed with n as the length (in bits) of the number - and that you cannot assume things like comparing, adding, modulor or multiplying to be O(1), because with arbitrariy-precision numbers these operations become more expensive with the size of the number.

The best currently known algorithm runs in O((log n)^6)

• @Brendan: Using precomputed results does not constitute an algorithm, at least not without specifying how you get those precomputed results and including that computation in the time analysis. – Michael Borgwardt May 8 '13 at 9:10
• No - Big O has A LOT of practial value. My point is that looking up a precomputed solution to X is not an algorithm that solves X unless you include the steps to do the precomputation. Suggesting otherwise is very similar to the apocryphal Marie Antoinette quote that people rioting because they have no bread should just eat cake. – Michael Borgwardt May 8 '13 at 10:43
• @Brendan: That way of looking at it is not even broken, it's completely missing the problem. You cannot solve an arbitrarily scalable problem by assuming that the solution already exists and you just have to look it up. The largest known prime number is 2^57,885,161 − 1. Now I want to know whether 2^57,885,715 − 1 is prime. How is "look it up in a bitfield" going to do that? – Michael Borgwardt May 8 '13 at 11:21
• @Brendan: If you really want to split hairs: the original poster wanted to know the time complexity of his specific code and was not interested in alternatives at all. But "look up a precomputed solution" is still not an algorithm, and it's completely meaningless to talk about Big-O when your solution only works on a size-limited version of the problem. – Michael Borgwardt May 8 '13 at 11:55
• @Brendan: This discussion is pointless. You have clearly demonstrated that you have no idea what the word "algorithm" even means. – Michael Borgwardt May 8 '13 at 15:20

Worst case - when the number is prime - is quite obvious O(sqrt(n)) Best case happens when number can be divided by 2,3,5,7,9. In these cases we will terminate the loop pretty soon in finite number of steps - O(1)

Now lets compute full average case for the algo:

On the interval [0,n] there are aprox n/ln(n) prime numbers.

The algo hits prime with probability of P1=1/ln(n)

The other numbers with probability of P2=1-ln(n)

Average case is O(sqrt(n))*1/ln(n)+O(1)*(1-ln(n)) We get rid of smaller part

=O(sqrt(n))/ln(n)

move ln(n) inside O()

=O(sqrt(n)/ln(n))

base of logarithm does not matter for big-O notation

= O(sqrt(n)/log(n))
• Composite numbers are not detected in constant time. For example if you check numbers up to a million, there are plenty that are products of two primes > 500. – gnasher729 Feb 19 '16 at 13:47
• constant time O(1) is only for the most fortunate case, the rest is O(sqrt(n)) – Katkov Feb 22 '16 at 19:33

The maximum execution time of this algorithm is O (sqrt (n)), which will be achieved if n is prime or the product of two large prime numbers.

Average execution time is tricky; I'd say something like O (sqrt (n) / log n), because there are not that many numbers with only large prime factors.

• regarding average case: for those who wonder why - On interval [0,n] there are aprox n/ln(n) prime numbers. For the algo in questioProbability of a prime number – Katkov Feb 19 '16 at 2:53