Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

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;
share|improve this question
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

2 Answers 2

up vote 7 down vote accepted

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)

share|improve this answer
@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
That's an entirely broken way of looking at it. If you do uint8_t myBitfield = 0x12 in your code; do you have to include the algorithm used to generate the 8-bit bitfield? – Brendan May 8 '13 at 10:53
@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: how can you possibly still miss the point: where does the value of that bitfield come from? Magic? And once you have hit, your lookup still only works for numbers up to that limit, whereas an actual algorithm does not have such a limit. – Michael Borgwardt May 8 '13 at 15:14

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.