|
Be the first user to complete this post
|
Add to List |
317. Check if given number is Prime - O(√N) Solution
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.
Example:
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)
Output:
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