9

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;
}
2
  • 4
    you loop from 3 to sqrt(number), this is enough info for you to figure out the rest... Commented May 8, 2013 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. Commented May 8, 2013 at 9:49

3 Answers 3

19

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)

18
  • 4
    @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. Commented May 8, 2013 at 9:10
  • 3
    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. Commented May 8, 2013 at 10:43
  • 5
    @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? Commented May 8, 2013 at 11:21
  • 7
    @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. Commented May 8, 2013 at 11:55
  • 3
    @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. Commented May 8, 2013 at 15:14
2

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))
2
  • 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
    Commented Feb 19, 2016 at 13:47
  • constant time O(1) is only for the most fortunate case, the rest is O(sqrt(n))
    – Katkov
    Commented Feb 22, 2016 at 19:33
0

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.

1
  • 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
    Commented Feb 19, 2016 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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