Prime Number

A prime number can be divided, without a remainder, only by itself and by 1. For example, 13 can be divided only by 13 and by 1, so it is a prime number.

In other words, When the only two factors of a number are 1 and the number, then it is a Prime Number.

Composite Number

A whole number that can be divided evenly by numbers other than 1 or itself e.g. 9 can be divided evenly by 3 (as well as 1 and 9), so 9 is a composite number.

We can "break apart" Composite Numbers into Prime Number factors.  And that is why they are called "Composite" Numbers because composite means "something made by combining things"

It is like the Prime Numbers are the basic building blocks of all numbers. And the Composite Numbers are made up of Prime Numbers multiplied together.

There are many puzzles in mathematics that can be solved more easily when we "break up" the Composite Numbers into their Prime Number factors. A lot of internet security is based on mathematics using prime numbers.

Java Implementation

So what should be the approach to write a java program to check whether a number is prime or not?

Naive Approach

• For given number n, start dividing n from 2 to (n-1)
• If we find any number (i.e. other than 1 and n) which can divide n without remainder, then n is not a prime number, else it is a prime number.

public static boolean isPrimeNaive(int n) {
    // 1 is not Prime and also not Composite.
    if(n==1)
    {
        return false;
    }
    
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Above program doesn't seem bad, but we can make it more efficient.

More Efficient Approach 

In this approach we will use two properties of prime numbers.

1) The only even prime number is 2. All other even numbers can be divided by 2 and hence they are not prime numbers.

2) Every composite number has at least one prime factor less than or equal to square root of itself.

In other words, the smallest prime factor of a composite number N is always less than or equal to √N.

This property can be proved using counter statement.

• Let a and b be two factors of n such that a*b = n  
• If a==b, then max possible value of a and b is √n because √n*√n=n
• If one factor is less than √n then other will be greater than √n
• If there is no such factor less than or equal to √n , then both factors would be greater than √n, but it's not possible.
• For example, If both are greater than √n, then a*b > √n*√n , which contradicts the expression a*b=n   i.e. √n*√n = n.
• so, that number must be prime if it doesn't have a factor less than or equal to √n.

Here is the Java implementation using above two properties

public static boolean isPrime(int n) {
        
    // 1 is not Prime and also not Composite.
    if(n==1)
    {
        return false;
    }

    // for 1st property - For all the even numbers != 2
    if (n>2 && n % 2 == 0)
        return false;

    // for 2nd property - for all the odd numbers > 2
    // Here we will try to find any one odd factor which is
    // less than or equal to square root of n 
    for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
        if (n % i == 0)
            return false;

    }
    return true;
}