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:

public class CheckPrimeNumber {
static void naiveMethod(int n){
System.out.print("O(N) Solution : ");
boolean isPrime = true;
for (int i = 2; i <n ; i++) {
if(n%i==0) {
System.out.println("Number " + n +" is not a prime no");
isPrime = false;
break;
}
}
if(isPrime)
System.out.println("Number " + n +" is a prime no");
//Time Complexity: O(N)
}
static void betterMethod(int n){
boolean isPrime = true;
System.out.print("O(N/2) Solution : ");
for (int i = 2; i <=n/2 ; i++) {
if(n%i==0) {
System.out.println("Number " + n +" is not a prime no");
isPrime = false;
break;
}
}
if(isPrime)
System.out.println("Number " + n +" is a prime no");
//Time Complexity: O(N/2) ~ O(N)
}
static void bestMethod(int n){
boolean isPrime = true;
System.out.print("O(√N) Solution : ");
for (int i = 2; i <=Math.sqrt(n) ; i++) {
if(n%i==0) {
System.out.println("Number " + n +" is not a prime no");
isPrime = false;
break;
}
}
if(isPrime)
System.out.println("Number " + n +" is a prime no");
//Time Complexity: O(√N)
}
public static void main(String[] args) {
int n = 13;
naiveMethod(n);
betterMethod(n);
bestMethod(n);
n = 15;
naiveMethod(n);
betterMethod(n);
bestMethod(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