Prime Number Program in Java

Methods to Write a Prime Number Program in Java

Now, let's discuss different methods to write the prime number program:

1. Brute Force Method: In the brute force method, we start a loop from 2 to the number itself (n). Inside the loop, we check if the number is divisible by any value between 2 and n-1. If it is divisible, we conclude that the number is not prime and break the loop. If the loop completes without finding any divisors, we declare the number as prime.

2. Optimized Method: The optimized method is an improvement over the brute force approach. Instead of checking divisibility up to n-1, we only need to check until the square root of n. This is because if a number is not prime, it must have at least one factor less than or equal to its square root. By reducing the range of divisors to check, we can significantly improve the efficiency of the program.

3. Using Built-in BigInteger Class: Java provides a built-in class called BigInteger that supports arbitrary-precision arithmetic. The BigInteger class has a method called isProbablePrime() that determines whether a given BigInteger is prime or not. This method uses the Miller-Rabin primality test, which is a probabilistic algorithm that efficiently determines the primality of large numbers. Using the BigInteger class simplifies the prime number program and handles large numbers efficiently.

4. Sieve of Eratosthenes: The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a given limit. It works by creating a boolean array of size n+1 (where n is the limit) and initializing all elements to true. Then, it starts from 2 and marks all multiples of 2 as non-prime. It continues with the next unmarked number (which is always prime) and marks its multiples as non-prime. This process is repeated until all numbers up to the square root of n are checked. The remaining unmarked numbers are the prime numbers.

Let’s see the different algorithms for writing Prime Number Programs in Java.

Program to Check Prime Number using a for loop

Java program to check if a given number is prime using a for loop:

import java.util.Scanner;

class PrimeNumber {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int num = sc.nextInt();
       
       if(isPrime(num)) {
           System.out.println(num + " is a prime number");
       } else {
           System.out.println(num + " is not a prime number");
       }
   }

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

You can also try this code with Online Java Compiler

Run Code

Input

13

Output

13 is a prime number

Explanation

This Java program checks if a given number is prime. It prompts the user for input, then utilizes a `for` loop to iterate from 2 up to the square root of the number. Within each iteration, it checks if the number is divisible by the current value of `i`. If a divisor is found, it concludes the number is not prime. If no divisors are found, it's a prime number. 

Program to Check Prime Number using a while loop

Java program to check if a given number is prime using a while loop:

• Java

Java

import java.util.Scanner;

class PrimeCheck {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int num = scanner.nextInt();
       
       if(isPrime(num)) {
           System.out.println(num + " is a prime number");
       } else {
           System.out.println(num + " is not a prime number");
       }
     
   }

   public static boolean isPrime(int num) {
       if (num < 2) {
           return false;
       }
       int i = 2;
       while (i <= Math.sqrt(num)) {
           if (num % i == 0) {
               return false;
           }
           i++;
       }
       return true;
   }
}

You can also try this code with Online Java Compiler

Run Code

Input

17

Output

17 is a prime number

Explanation

This Java program checks if a given number is prime using a `while` loop. It starts by prompting the user for input. The `isPrime` method iterates from 2 up to the square root of the number using a `while` loop, checking for divisibility in each iteration. If a divisor is found, it concludes the number is not prime. If no divisors are found, it deems the number as prime. 

Naive Approach for Writing Prime Number Program in Java

As per the definition, A number n is a prime number if there is no number b/w one and n that can divide n. 

We are going to use this simple fact to write our program.

• Java

Java

public class PrimeNumber {
    // function to check if a number is prime
    private static boolean isPrime(int number){
        // variable to store if the number is prime
        boolean isNumberPrime = true;
        
        /* 
           loop in the range [2,number-1] to check
           if there is any integer that can divide 
           the number.
        */
        for(int i=2; i<number; i++){
            if( (number % i) == 0 ) {
                isNumberPrime = false;
                break;
            }
        }
        return isNumberPrime;
    }

    public static void main(String[] args) {
        
        // Defining two number 7 and 8
        
        int number1 = 7;
        int number2 = 8;


        // checking if they are prime or not
        boolean result1 = isPrime(number1);
        boolean result2 = isPrime(number2);


        // Printing the result
        System.out.println(number1+" is "+((result1)? "a Prime number":" not a Prime number"));
        System.out.println(number2+" is "+((result2)? "a Prime number":" not a Prime number"));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

7 is a Prime number
8 is  not a Prime number

Explanation

We have made isPrime function to determine if a number is prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to number-1 to check if any number divides the “number”. If any integer exists between two and number-1 that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false.

Time and Space Complexity

• Looping over the range [2, number-1] will take O(n) operations, and hence the time complexity is O(n).
• We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

Optimised Approach to Write Prime Number Program in Java

Let’s see the factors of a number to find some pattern:

36 = (1,2,3,4),(6),(36,18,12,9).

We have kept factors of 36 in three groups. If we multiply a member of the first group by the respective member of the second group, we will get 36, i.e. 

1*36 = 36, 2*18 = 36, 3*12 = 36, 4*9 = 36.

So, when we check that if 36 is divisible by the member of the first group, then we are not required to check the same by the second group. This led to the observation that we only need to check factors until sqrt(n) to determine whether it is prime.

Let’s verify the fact with another number, 12.

12 = (1,2,3),(12,6,4).

We have only two groups in this case because 12 is not a perfect square. Here also, multiplying the respective members of the first and second groups will result in 12. So, we only need to check factors until sqrt(12) ~ 3 to determine whether it is prime.

Code in Java

• Java

Java

public class PrimeNumber {
    // function to check if a number is prime
    private static boolean isPrime(int number){
        // variable to store if the number is prime
        boolean isNumberPrime = true;


        /*
           loop in the range [2,sqrt(n)] to check
           if there is any odd integer that can divide
           the number.
        */
        for(int i = 2; i * i <= number; i++ ){
            if( (number % i) == 0 ) {
                isNumberPrime = false;
                break;
            }
        }
        return isNumberPrime;
    }


    public static void main(String[] args) {


        // Defining two number 49456 and 123677


        int number1 = 49456;
        int number2 = 123677;


        // checking if they are prime or not
        boolean result1 = isPrime(number1);
        boolean result2 = isPrime(number2);


        // Printing the result
        System.out.println(number1+" is "+((result1)? "a Prime number": "not a Prime number"));
        System.out.println(number2+" is "+((result2)? "a Prime number": "not a Prime number"));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

49456 is not a Prime number
123677 is a Prime number

Explanation

We have made isPrime function to determine if a number is a prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to sqrt(n) to check if any integer exists that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false. We are using the expression i * i <= number to stop the execution of the loop when the integer lies outside the mentioned range.

Time and Space Complexity

• Looping over the range [2, sqrt(n)] will take O(sqrt(n)) operations, and hence the time complexity is O(sqrt(n)).
• We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).

Program to Check Prime Number Using a Flag Variable

public class PrimeCheck {
    public static void main(String[] args) {
        int num = 29;
        boolean isPrime = true;

        if (num <= 1) {
            isPrime = false;
        } else {
            for (int i = 2; i <= num / 2; i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        if (isPrime)
            System.out.println(num + " is a Prime Number.");
        else
            System.out.println(num + " is not a Prime Number.");
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

29 is a Prime Number.

Explanation

This program uses a boolean flag to check if the number is divisible by any number other than 1 and itself. If it is, the flag is set to false, meaning the number is not prime.

Program to Check the Prime Numbers from 1 to 100

public class Prime1To100 {
    public static void main(String[] args) {
        for (int num = 2; num <= 100; num++) {
            boolean isPrime = true;

            for (int i = 2; i <= num / 2; i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.print(num + " ");
            }
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Explanation

This program uses a loop to check every number from 2 to 100. If the number passes the prime test, it is printed.

Program to Check Prime Numbers between Two Numbers

public class PrimeBetweenTwo {
    public static void main(String[] args) {
        int start = 50, end = 100;

        for (int num = start; num <= end; num++) {
            boolean isPrime = true;

            if (num <= 1) continue;

            for (int i = 2; i <= num / 2; i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.print(num + " ");
            }
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

53 59 61 67 71 73 79 83 89 97

Explanation

The program takes a range and checks each number within it. If a number is not divisible by any other number except 1 and itself, it is printed as a prime number.

Program to Check Prime Number Using Recursion

public class PrimeRecursion {
    public static boolean isPrime(int num, int i) {
        if (num <= 2)
            return (num == 2);
        if (num % i == 0)
            return false;
        if (i * i > num)
            return true;
        return isPrime(num, i + 1);
    }

    public static void main(String[] args) {
        int num = 29;
        if (isPrime(num, 2))
            System.out.println(num + " is a Prime Number.");
        else
            System.out.println(num + " is not a Prime Number.");
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

29 is a Prime Number.

Explanation

This recursive function checks if a number is divisible by any value starting from 2 up to the square root of the number. If not, it confirms the number as prime.

Frequently Asked Questions

How do you write a prime number program in Java?

In Java, write a program that iterates through numbers, checking for factors up to their square root. If a number has no factors other than 1 and itself, it's prime.

What is the method to find a prime number in Java?

The method involves iterating from 2 to the square root of the number and checking for divisibility. If the number is only divisible by 1 and itself, it's prime.

What are the first 10 prime numbers print? 

The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. These are natural numbers greater than 1 that have no divisors other than 1 and themselves.

What is the logic of a prime number?

A prime number is one that's only divisible by 1 and itself. To determine if a number is prime, iterate from 2 to its square root. If it's divisible by any number in this range, it's not prime; otherwise, it is.

Conclusion

In conclusion, we can say that prime number programs in Java are very important in computer science. They have diverse applications. We can find if a number is prime using various approaches. In this article, we improved approach by approach, and, finally, the most optimised algorithm has taken O(sqrt(n)) operations to determine if a number is prime.

Recommended Readings:

• Print Prime Numbers from 1 to N in Java
• Count Prime in Ranges
• The Largest Prime Number Possible from a Subsequence of a Binary String
• Find Any Prime Number P contains given Number N