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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class CheckPrimeNumber { static void naiveMethod(int n){ System.out.print("O(N) Solution : "); boolean isPrime = true; for (int i = 2; i

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