Finding and Checking Prime Numbers in Java With Examples [Latest]

What is a Prime Number?

A prime number is a natural number greater than 1 that is only divided by 1 and itself.

For example, 5 is a prime number because it can be divided by only 1 and 5.

Similarly, 6 is not a prime number because it can be divided by 1, 2, 3, and 6.

Algorithm to Find Prime Numbers between 1 and N

There are many algorithms to find a prime number within the given range. The “Sieve of Eratosthenes” is one of the popular and simple algorithms to find prime numbers up to a given range.

The algorithm to find prime numbers between 1 and N has the following steps.

1. Create a list of consecutive numbers from 2 to N i.e. (2,3,4…N).
2. Start with the first and the smallest prime number 2. Let’s say variable p=2.
3. Find the multiples of p i.e. 2p, 3p, 4p up to N and mark them in the list as not prime numbers. Note that the number p should not be marked itself.
4. Find the next number in the list that is not marked and follow the earlier step with it.
5. When the numbers in the list are exhausted, the algorithm is terminated. The list of numbers that are not marked are the prime numbers between 1 and N.

Below GIF gives a visual representation of the algorithm (Source: Wikipedia).

Java Implementation for Finding Prime Numbers between 1 and N

package com.journaldev.examples;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PrimeNumbers {
	public static void main(String[] args) {
		System.out.println(findPrimeNumbers(100));
	}
	// generating the list of prime numbers from 2 to the given number
	// using the Sieve of Eratosthenes algorithm
	private static List<Integer> findPrimeNumbers(int n) {
		// initialize the array with "true", index denotes the numbers from 0 to n.
		boolean[] primes = new boolean[n + 1];
		Arrays.fill(primes, true);
		//loop from 2 to x until x*x becomes greater than n
		for (int i = 2; i * i < n; i++) {
			// process if the number is not already marked
			if (primes[i]) {
				// find the multiples and mark them as false
				for (int j = i * i; j <= n; j += i)
					primes[j] = false;
			}
		}
		// populate the list of prime numbers from the array and return it
		List<Integer> primeNumbers = new ArrayList<>();
		for (int i = 2; i <= n; i++) {
			if (primes[i])
				primeNumbers.add(i);
		}
		return primeNumbers;
	}
}

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]

Algorithm to Check if a Number is Prime?

The simplest method to check if a number is prime is using the trial division.

For a given number N, check if there is a prime number M between 2 to √N (square root) that evenly divides it i.e. remainder is 0.

If there is a number M that evenly divides N, then N is not a prime number. Otherwise, N is a prime number.

Java Implementation to Check Prime Number

Here is the implementation to check if a number is prime or not. We will utilize the earlier defined method to find out the prime numbers between 2 and √N.

package com.journaldev.examples;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PrimeNumbers {
	public static void main(String[] args) {
		int number = 123456789;
		boolean isPrime = checkPrime(number);
		System.out.printf("%d is Prime: %b.n", number, isPrime);
		System.out.printf("%d is Prime: %b.n", 3511, checkPrime(3511));
		System.out.printf("%d is Prime: %b.n", 123, checkPrime(123));
	}
	// a number is not prime if there is a prime number between 2 to the square root of
	// num that evenly divides it
	private static boolean checkPrime(int num) {
		// get the prime numbers from 2 to square root of num.
		List<Integer> primes = findPrimeNumbers(Double.valueOf(Math.sqrt(num)).intValue());
		System.out.println(primes);
		for (int i : primes) {
			if (num % i == 0) {
				System.out.printf("%d is divided by %d.n", num, i);
				return false;
			}
		}
		return true;
	}
}

References