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.

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

__________________________________________________
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.
__________________________________________________

  • lipsa patel

    The condition for “For Loop” in better method is wrong

    for (int i = 2; i <=Math.sqrt(n) ; i++) {

    should be

    for (int i = 2; i <= n/2 ; i++) {

    • tutorialhorizon

      Thanks lipsa. Modified the code.

%d bloggers like this: