Home / Java / Loop / Recursion / Java Program to Check If a Number Is a Prime or Not

Java Program to Check If a Number Is a Prime or Not

in , ,
Prime number

Java program to check if a number is a prime or not has been shown here. A positive number n is called a prime, if it does not have any divisor except 1 and n. For example if n = 13, it is prime but if n = 10, it is not prime as 10 is divisible by 2 and 5 apart from 1 and 10. The algorithm, pseudocode and time complexity of the program have been shown below.






1. Algorithm to check if a number is a prime or not


1. Take a positive number n as input.

2. Check for each i $\in$ [2, $\sqrt{n}$], if n is divisible by i

3. If step 2 is true for atleast one i, then n is not a prime.

4. If step 2 is false for each i, then n is a prime.




2. Pseudocode to check if a number is a prime or not


Input : A postive number $n$

Output : $n$ is a prime or not a prime

1. Procedure checkPrime($n$):

2. $flag \leftarrow 0$

3. Repeat for $i \in [2, \sqrt{n}]$:

4. If $n \mod i$ = 0:

5. $flag \leftarrow 1$

6. break

7. If $n = 1$

8. Return "not a prime"

9. Else:

10. If $flag = 1$:

11. Return "not a prime"

12. Else:

13. Return "a prime"

14. End Procedure





3. Time complexity to check if a number is a prime or not


Time Complexity: O($\sqrt{n}$)

Where n is the input number.





4. Program & output to check if a number is a prime or not




4.1. Java Program & output to check if a number is a prime or not using iteration

Code has been copied
/*********************************
    	alphabetacoder.com
Java program to check if a number 
is a prime or not using iteration
***********************************/

import java.util.Scanner;
import java.lang.Math;

class Main {
    public static void main(String[] args) {
        // declare instance of Scanner class
        Scanner sc = new Scanner(System.in);

        // delclare variables
        int n, i, flag = 0;

        // take inputs
        System.out.print("Enter the number = ");
        n = sc.nextInt();

        //check if n is a prime or not
        //If n has divisor between 2 and
        // square root of n, then 
        // n is not prime else n is prime
        for (i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                flag = 1; // mark as not prime
                break; // exit from loop
            }
        }

        // dispay the result
        if (n == 0 || n == 1)
            System.out.println(n + " is neither a prime nor a composite!");
        else {
            if (flag == 0)
                System.out.println(n + " is a prime!");
            else
                System.out.println(n + " is not a prime!");
        }
    }
}

Output

Enter the number = 79

79 is a prime!





4.2. Java Program & output to check if a number is a prime or not using recursion

Code has been copied
/*********************************
	 alphabetacoder.com
Java program to check if a number 
is a prime or not using recursion
***********************************/

import java.util.Scanner;
import java.lang.Math;

class Main {
    // recursive function to check 
    // if a number is prime or not
    // check divisor upto square root of num
    int check_prime(int num, int i) {
        // return 1, as num is prime
        if (i > Math.sqrt(num))
            return 1;
        // return 0, as num is not prime
        if (num % i == 0)
            return 0;
        // call function
        return check_prime(num, i + 1);
    }

    public static void main(String[] args) {
        // declare instance of Scanner class
        Scanner sc = new Scanner(System.in);

        // declare object of Main class
        Main obj = new main();

        // delclare variables
        int n;

        // take inputs
        System.out.print("Enter the number = ");
        n = sc.nextInt();

        //check if n is a prime or not
        // by calling the function
        // if the function returns 1, 
        // it is considered prime else
        // it is considered not prime
        if (n == 0 || n == 1)
            System.out.println(n + " is neither a prime nor a composite!");
        else {
            if (check_prime(n, 2) == 1)
                System.out.println(n + " is a prime!");
            else
                System.out.println(n + " is not a prime!");
        }
    }
}

Output

Enter the number = 13

13 is a prime!





Labels: , ,