Objective: Given a number, write a program to check if the number is prime or not.
Prime Number: A number is called a prime number when number is not divisible by 1 or by number itself. 1 is not considered as prime number.
N = 10 Output: ‘10’ is not a prime number N = 13 Output: ‘13’ is a prime number
Naïve Solution – Iterate through 2 to n-1 and check if given number is divisible by any number between 2 to n-1, if yes then number is not prime else it is prime. Time Complexity: O(N)
Better Solution– If you look closely, we do not have check all the number from 2 to n-1, once we check from 2 to n/2 , we will get our answer since any number greater than n/2 , cannot divide n. Time Complexity: O(N/2) or O(N)
Best Solution: Now can we do any better than n/2. Actually yes and answer is √n. But how???
- Let’s say number is n is not a prime number, that means there are two numbers which products to n (neither p nor r is 1). Say p*q = n.
- Means in (p, q), one of these two will be greater than equal to √n and one of them is less than equal to √n. Let’s see one example.
N = 64, √64 = 8 p*q = 64 2*32 = 64 4*16 = 64 8*8 = 64 16*4 = 64 32*2 = 64 So observe closely unique pairs are (2, 32), (4, 16) and (8, 8) after that p and q exchange the values. So it makes sense to validate till from 2 to 8 after that it will be repetitive.
Time Complexity: O(√N)
Code for all three solutions:
O(N) Solution : Number 13 is a prime no O(N/2) Solution : Number 13 is a prime no O(√N) Solution : Number 13 is a prime no O(N) Solution : Number 15 is not a prime no O(N/2) Solution : Number 15 is not a prime no O(√N) Solution : Number 15 is not a prime no