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)
i*i<=n.........
kindy correct.........
your code not working for 9.
it should be i*i<=n
(I know it's late, but....I had to)
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.