Home

Learning Hub

Articles

Prime Number Program in Java: A Detailed Guide

Java is a suitable language to check for prime numbers in a program. Prime numbers are fundamental mathematical concepts that everyone must know. Prime numbers are important in various fields like cryptography where they are used in algorithms like RSA, etc. But what is a Prime number? Any natural number larger than one that is not the product of two smaller natural numbers is known as a prime number. A prime number in simple terms is that number that is only divisible by 1 (one) or by itself.

Determining if a given number is prime is a typical challenge in programming. However, if you first examine an implementation of prime numbers using the Java program, you might find it easier to understand the concepts of loops, conditionals, and algorithm efficiency. In this article, we will discuss different approaches to check whether or not a number is prime in Java. We will explore various approaches with their detailed explanations and with each algorithm for approaches and code examples.

What is a Prime Number?

A fundamental consequence of number theory is that there are an unlimited amount of prime numbers, as stated by Euclid’s theorem. A prime number is a number that is divisible by 1 and itself. A prime number contains two factors i.e., 1 and the number itself. For example, the first ten prime numbers include 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29. The numbers left after the prime number are known as composite numbers. Let’s see some facts about prime numbers:

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• There are infinite numbers of prime numbers
• The gap between two prime numbers can be short or long depending on the number.
• 2 is the smallest prime number in mathematics.
• We can use prime numbers larger than 3 as 6k+1 or 6k−1 (for some natural number k).
• Zero (0) and one (1) are not prime numbers.
• In maths, two prime numbers are always coprime of each other.
• All prime numbers except 2 (which is even) are odd numbers.

Why Choose Java For Checking Prime Numbers?

Java is a popular and versatile programming language that offers several advantages for tasks like checking prime numbers:

• Platform Independence: Java has a feature called Platform Independence, which is denoted by the phrase “write once, run anywhere.” The idea is that any program can be run on any device that has a Java Virtual Machine (JVM) installed, this results in great portability.
• Strong Standard Library: One area where Java shines brightly is its Strong Standard Library: it consists of many different tools and utilities through which various tasks can be simplified, including maths operations.
• Performance: Using the Just-In-Time (JIT) compiler, it helps improve the robustness of Java’s performance because it optimises bytecode into native machine code during runtime.
• Memory Management: Memory Management is taken care of by Java through an automatic way – garbage collection, leading to lesser possibilities of memory leaks and pointer-related bugs.
• Multi-threading: Java has parallel processing support built into it known as multithreading that can enable using multiple processors at the same time to optimise performance for large-scale computations easily as a result of this feature.

Algorithm to Check Prime Number in Java

Checking a prime number using a Java program is simple and easy. Below is a detailed and generalised algorithm for checking if a number is prime or not in Java:

1. Take an input number (num)
2. Base condition check:
   1. If num is less than or equal to 1, the number is not prime.
3. Check Divisibility for the prime number:
   1. If num is divisible by 2 or 3 and is greater than these numbers, it is not a prime.
4. Trial division
   1. For all integers i starting from 5, check if num is divisible by i or i+2 (this covers all numbers of the form 6k + 1 or 6k – 1).
   2. If any such i divides num, it is not a prime. Continue this check-up to the square root of num.

Pseudocode

Let’s now understand the pseudocode for the discussed algorithm that you can apply in Java language and other languages. The pseudocode for checking if a number is prime or not in Java:

Explanation:

In this pseudocode, we have outlined the basic algorithm to find whether a given number is a prime number or not.

• The algorithm has a function that takes an input parameter (num).
• We then perform a basic check:
  • If a number is less than or equal to 1, return false.
  • If num is 2 or 3, we return true as they both are prime.
  • If num is divisible by 2 or 3, return false.
• After that, an optimization trial is done:
  • We start from 5 and check numbers that form 6k + 1 or 6k – 1 as all prime numbers greater than 3 can be expressed as 6k + 1 or 6k – 1.
  • For each i in this expression: We divide num by i or i + 2 and if it is divisible, we return not a prime. Continue this check-up to the square root of num.

Different Approaches

In the Java language, there are various approaches by which you can check prime numbers in a Java program. We will discuss various approaches by which you can find whether a given number is prime or not:

• Using Simple Loop Program
• Using Methods in Java
• Using Squareroot (Optimised)
• Using Sieve of Eratosthenes
• Miller-Rabin Method

Let’s discuss these approaches in detail with the code examples, their explanation, and the respective output of each example.

1. Using Simple Loop Program

The simple program to check for a prime number is using the loops including for loop or while loop in Java.  As we know there can’t be a divisor of number (n) greater than or equal to n/2, therefore we divide the number (n) with only those numbers that are less than or equal to n/2. Therefore, in this approach, we will use this method to check for primes using for loop and while loop.

Below is the algorithm for checking whether a number is prime or not using a simple loop:

• Take the input number (n).
• Initialise a counter cnt to 0 to count the number of divisors.
• Now, check for numbers less than equal to 1:
  • If n is less than or equal to 1, return not a prime.
• Count the number of divisors:
  • Use a for/while loop to iterate from 1 to n/2.
  • For each number i in the range, check if n % i == 0.
  • If true, increment the counter cnt.
• Check for prime based on cnt value:
  • If cnt (the number of divisors) is greater than 1, return not a prime, else return prime”.

For Loop

Let’s see a detailed example using a for loop to check whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using a simple for loop to check for prime numbers in Java. Here, If the value of num is <= 1, it immediately reports that the number is not a prime one. It loops up to half of the num and checks how many times the num is divisible without any remainder. If there are more divisors than just one, then the number is said to be a non-prime, else a prime number.

While Loop

Let’s see a detailed example using the While loop to check whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using a simple while loop to check for prime numbers in Java. Here, If the value of num is <= 1, it immediately reports that the number is not a prime one. It loops up to half of the num and checks how many times the num is divisible without any remainder. If there are more divisors than just one, then the number is said to be a non-prime, else a prime number.

2. Using Methods in Java

In this approach, we will use a custom method to check for prime numbers in Java. We can put the logic for determining whether a number is prime into a different method to make the code method-based. This new method will then be called by the main function, which will handle the output.

Below is the algorithm for checking whether a number is prime or not using methods in Java:

• Take the input number (n).
• Now, check for numbers less than equal to 1:
  • If n is less than or equal to 1, return not a prime.
• We then use a while loop to count the number of divisors of the number.
• Lastly, it returns true if the number has at most one divisor (indicating it is prime), and false otherwise indicating non-prime.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the method-based approach to check for prime numbers in Java. Here, to check if a given number num is prime by invoking an auxiliary function called isPrime has been illustrated above. In the main method, user input num is taken and passed as a parameter to isPrime(num). If at all num <= 1, the call to isPrime immediately returns false: otherwise, it begins traversing from 2 up to num-1 searching for any factors of num other than 1 and itself. If such a divisor is found during the search process, false is returned, meaning num cannot be termed prime.

However, when no such divisors are found till the end of an iteration, we return true which means a prime number.

3. Using Squareroot (Optimised)

The square root of a number can also be used to check for prime numbers in the C program. This approach is an optimised version of the above approach as we reduce the number of checks. Here, instead of checking all numbers up to n−1, we only check up to the square root of n. Below is the algorithm for checking whether a number is prime or not using a square root:

• Take the input number (n).
• Now, check for numbers less than equal to 1:
  • If n is less than or equal to 1, return not a prime.
• We then use a for loop from 2 to sqrt(n):
  • For each number i in this range, check if n is divisible by i.
  • If n is divisible by any i, then n is not a prime number.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using an optimised square root method to check for prime numbers in Java. Here, It starts by checking whether the value of num is <= 1. In this case, it will return false indicating that num is not a prime number. Then it goes through a loop starting from 2 up to the square root of num to check for divisibility. If num is divisible by any number within this range, then it returns false. Otherwise, if no divisors are found, it returns true which confirms that num is a prime number.

4. Using Sieve of Eratosthenes

Another approach is using the Sieve of Eratosthenes. It is the most efficient algorithm for finding whether a number is a prime number or not. In this approach, a limit is set on which the algorithm works. It starts at 2 and indicates the multiples of every prime.

Below is the algorithm for checking whether a number is prime or not using a sieve of Eratosthenes:

• Take the number n (upper limit).
• Create a boolean array prime[0..n] and initialise all entries as true. If i is not a prime, a value in prime[i] will be false; otherwise, it will be true.
• Initialise prime[0] and prime[1] to false: 0 and 1 are not prime numbers.
• Loop through numbers from 2 to sqrt(n):
  • If prime[p] is true for each given number p, then mark all multiples of p as false (not prime).
• Give all of the indices i for which prime[i] is true. These are the prime numbers up to n.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the Sieve of Eratosthenes algorithm method to check for prime numbers in Java. With this algorithm, we are finding all primes in a range of 1 to n using the Sieve of Eratosthenes algorithm. By removing non-prime integers in subsequent iterations of the program, this method effectively finds all prime numbers up to n. As such, it is appropriate for applications that need to determine the prime numbers within a given range.

5. Miller-Rabin Method

Miller-Rabin is a probabilistic method used for checking the prime numbers in programming. A procedure that uses probability to assess whether a given integer is likely to be prime is the Miller-Rabin test. Although it is more widely used than Fermat’s method, this approach is also probabilistic. It can be done more than once to lower the likelihood of false positives.

Below is the algorithm for checking whether a number is prime or not using a Miller-Rabin primality test:

• Take input of k (number of iterations).
• Special Cases:
  • If n <= 1, return false (not prime).
  • If n <= 3, return true (prime).
  • If n is even, return false (not prime).
• Write n-1 as d * 2^r:
  • Initialize d to n-1.
  • While d is even, divide d by 2 and increment r.
• Perform k iterations of the test:
  • For each iteration:
    • Pick a random integer a in the range [2, n-2].
    • Compute x = a^d % n using modular exponentiation.
    • If x == 1 or x == n-1, continue to the next iteration.
    • While d is not n-1:
      • Square x and take modulo n.
      • Double d.
      • If x == 1, return false.
      • If x == n-1, break.
    • If none of the conditions in step 4 are met, return false.
  • If all iterations pass, return true.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the Miller-Rabin test algorithm to check for prime numbers in Java. We have three functions in this example: the modExp() function uses the modular exponentiation (base^exp) % mod through repeated squaring efficiently. Then, the millerTest() function forms the essence of this approach where a random base ‘a’ is generated within the range [2, n-2] and a ^ d % n is computed. If x turns out to be either 1 or n-1, true is returned. Otherwise, the squaring continues until d equals n-1 by checking if x is equal to one of these values.

Finally, we have an isProbablePrime() function which checks if a number ‘n’ is probably prime by running the Miller test k times after handling edge cases and obtaining d from n-1.

In this article, we looked at a few different ways to determine whether a given number is prime in Java. We looked at easy methods like the optimised square root and simple loop programs. We also explored some optimal and efficient algorithms like the Sieve of Eratosthenes to compute prime numbers up to a predetermined threshold efficiently. We have also seen the probabilistic method known as the Miller-Rabin Primality Test that runs for k times to check whether a given number is prime or not. All of these approaches have their pros and cons, and it’s up to you which approach best suits your needs.