Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
3  
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

1 Answer 1

up vote 6 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
    
The fastest known algorithm is to use a pre-computed bit field. It's O(1), but costs "(max_number/2 + 7)/8" bytes (e.g. 128 MiB for 32-bit signed integers). –  Brendan May 8 '13 at 8:58
1  
@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
1  
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
1  
@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
4  
@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

Your Answer

 
discard

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.