Number Theory: Primality Test in O(sqrt(n))

#numbertheory #datastructures

A number is said to be prime if it is divisible by a number other than 1 and itself.
1 is not considered to be a prime number.

Primality Test is to determine whether the input integer is a prime number or not.

For instance,

5: Prime Number
12: Not a prime number
7: Prime Number
14: Not a prime number

For instance, 12 is prime because it is divisible by 2,3 and 6.

Approach 1

bool isPrime(int n) {

  if (n == 1) {
    return false;
  }

  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false;
  }

  return true;
}

In this method, we traverse from 1 to n, hence the time complexity, in this case, is: O(n).

Approach 2: The Better One

Now, consider a pair a*b = n. Here, a and b are the factors of n.
For instance,

n = 12
(a,b) can be (1,12),(2,6),(3,4)

On observing the equation, we can infer that the maximum value of a and b can be the square root of n.

sqrt(n)*sqrt(n) = n

Since, if both of the values go beyond sqrt(n), then a*b would be greater than n.

Also, If a is less than sqrt(n), then b will be greater then sqrt(n).
Similarly, if a is greater than sqrt(n), b will be smaller than sqrt(n).

We can conclude that one of the numbers is <= sqrt(n), and the other one is >= sqrt(n).

And to prove that n is prime, we just need to find one of the numbers - a or b.
If no such number exists, it means that n is not prime.

Hence, to do the primality test, we need not run loop till n, this can be done by running the loop till sqrt(n) itself.

bool isPrime(int n) {

  if (n == 1) {
    return false;
  }

  for (int i = 2; i*i < n; i++) {
    if (n % i == 0) return false;
  }

  return true;
}

Note: Using the libraries such as sqrt() can sometimes give unexpected values. Hence, instead of checking for i < sqrt(n) in the for loop, we check for i*i< n.

The loop runs from 2 to sqrt(n), hence the time complexity would be O(sqrt(n)).

Keep Coding! :)

Top comments (3)

Saumya Verma • Jan 23 '21

There is this article that optimized it furthermore....
geeksforgeeks.org/primality-test-s...
Because I checked it over some coding platform with the correction of @starlord and it still fails to pass some test cases.