Check if given number is Prime – O(√N) Solution – Java Program

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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: