Check Prime number- Java Code

Advice

 

 

What is Prime Number?

 

• Check what it is in the Math book of standard 4 or search online.

Which Number has only two factors 1 and number itself.

Prime Numbers

Now it is time for Code

First Algo.

• Suppose Number is N
• We need to check N is divisible by numbers between 2 to N-1. For that, we can use a loop from 2 to N-1.

public boolean isPrime(int n){
       
        for(int i = 2; i <= n-1; i++){
            if(n%i == 0){
                return true;
            }
        }
        return false;
}

• Time Complexity of this function is O(n).

Time Complexity Graph

Second Algo.

• We do not need to divide N with all numbers 2 to N-1.
• We can half the set 2 to N/2.

public boolean isPrime(int n){
       
        for(int i = 2; i <=  (n/2 +n%2); i++){
            if(n%i == 0){
                return true;
            }
        }
        return false;
}

• Time Complexity of this function is O(n/2).

Tracing

N = 5

i = 2 to 5/2= 2

      i = 2 -> 5%2 != 0

      i = 3 -> 5%3 != 0

Third Algo.

public static boolean isPrime(int n){
       
        for(int i = 2; i <= Math.sqrt(n); i++){
            System.out.println(i);
            if(n%i==0){
                return false;
            }
        }
        return true;
}

• Time Complexity of this function is O(√n).

Posted by : Denes Vaghani March 18, 2020 Tags : Algorithm

Subscribe by Email

Follow Updates Articles from This Blog via Email