**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)**

**Code for all three solutions:**

**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