How to find Prime Numbers using Java Programming Language

Introduction

In this example we will see how to find prime numbers using Java programming language between 1 and 1000. We will also use Java 8 IntStream API to find prime numbers. We will actually compute prime number between given ranges, let’s say from i to n. So you can replace the starting (i) and ending (n) ranges. A number is a prime number if it is divisible by 1 and itself only.

We can find out prime numbers for a given range in several ways. We will create different examples below to find out prime numbers using Java between 1 to 1000.

Prerequisites

Java, Eclipse

Using Loops Only

We will create our first example to find prime numbers.

To find a prime number between given ranges we will check using two loops in the following manners, starting from 2 (i) to n (n being integer value) :

have a function for determining prime number
Verify whether the given number is prime by checking divisibility (using modulo operator) from 2 to n using a loop
if it’s divisible, then it’s not a prime number

The following function checks a particular number is prime or not:

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

Now we will create a function that will find all prime numbers between a range:

public static void printPrimeUpto(int num) {
	String sep = "";
	int i = 2;
	while (i <= num) {
		if (isPrime(i)) {
			System.out.print(sep);
			System.out.print(i);
			sep = ", ";
		}
		i++;
	}
}

Usage:

public static void main(String[] args) {
	printPrimeUpto(1000);
}

Executing the above function will give you output as shown below:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

The above output displays all prime numbers between 1 and 1000.

Using Previous Prime Numbers

Now we will improve the above algorithm to find prime numbers. So you can improve on it by observing that you have to only check divisibility by previous prime numbers:

program will keep track of all prior primes as it discovers, starting from 2, 3, etc.
then another function has to check divisibility by previous prime numbers only
If a number is not divisible by any of the previous prime numbers, it will be a new prime

For example, 13 is not divisible by 2, 3, 5, 7 or 11. So 13 is the prime number.

The below function checks whether a given number is prime or not. We pass also previous prime numbers as a second argument. Here we only divide the number by list of previous prime numbers to check the number is prime or not.

public static boolean isPrime(int num, List<Integer> primeNumbers) {
	if (num == 2) {
		return true;
	}
	for (int i = 0; i < primeNumbers.size(); i++) {
		if (num % primeNumbers.get(i) == 0) {
			return false;
		}
	}
	return true;
}

The following function prints all prime numbers up to 1000. It also adds previous prime numbers in the list. You can also return the final prime numbers in a list from the method.

Initially we have added prime

public static void printPrimeUpto(int num) {
	String sep = "";
	int i = 2;

	List<Integer> primeNumbers = new ArrayList<>();
	primeNumbers.add(2);

	while (i <= num) {
		if (isPrime(i, primeNumbers)) {
			if (i != 2)
				primeNumbers.add(i);
			System.out.print(sep);
			System.out.print(i);
			sep = ", ";
		}
		i++;
	}
}

Usage:

public static void main(String[] args) {
	printPrimeUpto(1000);
}

Executing the above method will give you below 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Stopping at (n/2)+1

Further improvement can be done. You can stop at (n/2)+1, if a given number is not divisible by all the primes up to (n/2)+1, then you won’t find any larger number. For example, for the given number 13, you can stop at 7.

The only function has to be modified is given below:

public static boolean isPrime(int num, List<Integer> primeNumbers) {
	if (num == 2) {
		return true;
	}
	for (int i = 0; i < primeNumbers.size() / 2 + 1; i++) {
		if (num % primeNumbers.get(i) == 0) {
			return false;
		}
	}
	return true;
}

The output will be same as we have seen in previous section.

Using Counter Variable

Here we will keep track using counter variable to determine whether a given number is prime or not.

We will only modify the isPrime() method from the first approach of this tutorial.

public static boolean isPrime(int num) {
	int counter = 0;

	for (int i = num; i >= 1; i--) {
		if (num % i == 0) {
			counter = counter + 1;
		}
	}

	if (counter == 2) {
		return true;
	}

	return false;
}

Using Java 8 IntStream

We will find prime numbers using Java 8’s IntStream API. We can modify the isPrime() method from the first approach of this tutorial.

public static boolean isPrime(int num) {
	return IntStream.rangeClosed(2, num / 2).noneMatch(i -> num % i == 0);
}

That’s all. Hope you got an idea how to find prime numbers between a range of integers. You also got idea how to check a particular number whether it is a prime or not.

Source Code

Download

Thanks for reading.

Roy Tutorials