How to generate an Array of Prime numbers in Java - Sieve of Eratosthenes Algorithm Example

Hello guys, I have said many times that a good knowledge of Data Structure and Algorithms is the first step towards becoming a better programmer and that's why I share a lot of Data structure and Algorithm stuff in this blog. To continue the tradition, I am going to share an interesting algorithm today, The Sieve of Eratosthenes algorithm, which can be used to generate prime number up to a given number. There are many occasions when you need to generate all prime numbers up to a specified integer and one algorithm which is most often used to generate prime numbers is theSieve of Eratosthenes Algorithm.Surprisingly, not many developers know about this algorithm, particularly Java programmers, which is mainly because not doing enough competitive programming.

Sieve of Eratosthenes is an ancient Greek algorithm to find all prime numbers up to a given number and named after the famous Greek mathematician Eratosthenes. He was the first man to calculate the circumference of the earth and also known for working on calendars with leap years.

If you don't remember, a prime number is a whole number which is either divisible by 1 or itself like 2, 3 and 5. You can see they are not divisible to any positive whole integer.

In other words, a prime number doesn't have a factor other than 1 or itself. You can use this algorithm to generate prime numbers from 1 to 100 or up-to any maximum value.

In this tutorial, you will not only learn how Sieve of Eratosthenes algorithm works but also we will generate prime numbers using this algorithm and verify whether all number generated is actually prime or not.

Btw, if you are new to Algorithms and Data Structure, I suggest you go through a good, comprehensive online course like Data Structures and Algorithms: Deep Dive Using Java  to learn the basics and brush up the fundamentals. It's both comprehensive and affordable as I bought this course on just $11 on Udemy flash sale.

How Sieve of Eratosthenes Algorithm works

The Sieve of Eratosthenes algorithm is quite simple. You create an array of larger than 1 by a specified integer, so that index of the array represents the actual integer stored on it. Then you start with 2 because 0 and 1 are not considered prime.

A prime number is either divisible by 1 or by itself, it doesn't have any other factor. Since 2 is a prime number, we mark this as prime and cross out all its multiple because they won't be prime, Why? because prime numbers don't have any factor other than 1 and if a number is multiple of 2 it means it is divisible by 2, hence not prime.

In order to cross all numbers which are multiplied by 2, we just skip our array counter by 2, which means 2, 4, 6, 8 all are multiples of 2 and they will be crossed. Next number in the array is 3, now 3 is also not divisible by anyone so its a prime and we mark it as prime and again crossed out all multiples of 3 because they won't be prime.

In order to cross out multiples of 3, we skip array counter by 3, which means 3, 9, 12, 15 all are crossed. Now, Next number is 4 but it's already crossed because it was multiple of 2 so we skip to the next number which is 5.

Again 5 is a prime number so we mark it as prime and cross out all numbers which are multiples of 5 because they won't be prime as they are divisible by 5. In order to cross all multiples of 5, we just increase array counter by 5, so numbers like 10, 15, 20, 25 will be crossed out.

We continue this process until we reach at the square root of a given number because every multiple in the array has a prime factor that is less than or equal to the square root of the given number, so we don't have to cross out multiples of numbers larger than that root. For example, in order to find all prime numbers between 1 to 100, it's enough to check until 10.

If you are interested in learning more about such Algorithms, I also suggest you check out Algorithms and Data Structures - Part 1 and 2  on Pluralsight. Another awesome online course on Algorithms.

Btw, you would need a Pluralsight membership to access this course, which cost around $29 per month or $299 per year. If you don't have the membership, you can still access this course by using their 10-day free pass which allows 200 minutes of access to their 5000+ online courses on the latest technology, worth trying.

Sieve of Eratosthenes Algorithm Implementation in Java

Here is our Java program which implements the logic to generate prime numbers using Sieve of Eratosthenes Algorithm in Java Programming language:

import org.junit.Test; import static org.junit.Assert.*; /** * This class Generates prime numbers upto a given limit using the * Sieve of Eratosthenes algorithm. In this algorithm, we create * an array of integers starting from 2, then find the first uncrossed * integer, and cross out all its multiple. The process is repeated * until there are no more multiples in the array. */ public class PrimeNumberGenerator { private enum Marker{ CROSSED, UNCROSSED; } private static Marker[] crossedOut; private static int[] primes; public static int[] generatePrimeNumbersUpto(int limit){ if(limit < 2){ return new int[0]; }else{ uncrossIntegerUpto(limit); crossOutMultiples(); putUncrossedIntegersIntoPrimes(); return primes; } } private static void uncrossIntegerUpto(int limit) { crossedOut = new Marker[limit + 1]; for(int i = 2; i<crossedOut.length; i++){ crossedOut[i] = Marker.UNCROSSED; } } private static void crossOutMultiples() { int iterationLimit = determineIterationLimit(); for (int i = 2; i<= iterationLimit; i++){ if(notCrossed(i)){ crossOutMultipleOf(i); } } } private static int determineIterationLimit() { // Every multiple in the array has a prime factor // that is less than or equal to the square root of // the array size, so we don't have to cross out // multiples of numbers larger than that root. double iterationLimit = Math.sqrt(crossedOut.length); return (int) iterationLimit; } private static boolean notCrossed(int i) { return crossedOut[i] == Marker.UNCROSSED; } private static void crossOutMultipleOf(int i) { for(int multiple = 2*i; multiple < crossedOut.length; multiple += i){ crossedOut[multiple] = Marker.CROSSED; } } private static void putUncrossedIntegersIntoPrimes() { primes = new int[numberOfUncrossedIntegers()]; for(int j = 0, i = 2; i<crossedOut.length; i++){ if(notCrossed(i)){ primes[j++] = i; } } } private static int numberOfUncrossedIntegers() { int count = 0; for(int i = 2; i<crossedOut.length; i++){ if(notCrossed(i)){ count++; } } return count; } }

Unit test to Check Prime Number in Java

And,  here are some of the units tests to check whether our program is working properly or not

import static org.junit.Assert.*; import org.junit.Test; /** * Junit test cases to test our Sieve of Eratosthenes algorithm * for generating prime numbers upto a given integer. * @author WINDOWS 8 * */ public class PrimeNumberGeneratorTest{ public PrimeNumberGeneratorTest(){ System.out.println("Generator prime numbers using" + " Sieve of Eratosthenes algorithm"); } @Test public void testPrimes(){ int[] primeUptoZero = PrimeNumberGenerator.generatePrimeNumbersUpto(0); assertEquals(0, primeUptoZero.length); int[] primeUptoTwo = PrimeNumberGenerator.generatePrimeNumbersUpto(2); assertEquals(1, primeUptoTwo.length); assertEquals(2, primeUptoTwo[0]); int[] primeUptoThree = PrimeNumberGenerator.generatePrimeNumbersUpto(3); assertEquals(2, primeUptoThree.length); assertEquals(2, primeUptoThree[0]); assertEquals(3, primeUptoThree[1]); int[] primeUptoHundred = PrimeNumberGenerator.generatePrimeNumbersUpto(100); assertEquals(25, primeUptoHundred.length); assertEquals(97, primeUptoHundred[24]); } @Test public void testExhaustive(){ for(int i = 2; i<700; i++){ verifyPrimeList(PrimeNumberGenerator.generatePrimeNumbersUpto(i)); } } private void verifyPrimeList(int[] listOfPrimes) { for(int i = 0; i<listOfPrimes.length; i++){ verifyPrime(listOfPrimes[i]); } } private void verifyPrime(int number) { for (int factor = 2; factor < number; factor++){ assertTrue(number%factor != 0); } } }

and here is the result of our Unit test, all passed

That's all about how to generate prime numbers up to a specified integer using Sieve of Eratosthenes algorithm. This is a very efficient algorithm to generate a large number of prime numbers and can be used to solve complex programming problems where you need an array of prime numbers.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java 9 by Heinz Kabutz

Introduction to Algorithms by Thomas H. Corman

50+ Data Structure and Algorithms Problems from Interviews

If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :

• How to check if LinkedList contains any cycle in Java? (solution)
• 10 Points about Array in Java? (must know facts)
• How to find top two maximum on integer array in Java? (solution)
• Write a method to check if two String are Anagram of each other? (method)
• Write a program to find first non repeated characters from String in Java? (program)
• How to check if a number is binary in Java? (answer)
• Write a program to check if a number is Prime or not? (solution)
• Write a method to count occurrences of a character in String? (Solution)
• How to check if a number is Armstrong number or not? (solution)
• Write a Program remove duplicates from an array without using Collection API? (program)
• How to reverse String in Java without using API methods? (Solution)
• Write a method to remove duplicates from ArrayList in Java? (Solution)
• Write a program to check if a number is a Palindrome or not? (program)
• Write a program to check if the Array contains a duplicate number or not? (Solution)
• How to find the Fibonacci sequence up to a given Number? (solution)
• How to prevent Deadlock in Java? (solution)
• How to find the largest prime factor of a number in Java? (solution)
• How to calculate a factorial using recursion in Java? (algorithm)
• How to declare and initialize a two-dimensional array in Java? (solution)
• Write a program to find a missing number in a sorted array? (algorithm)
• How to find the largest and smallest number in an array? (solution)
• Write a function to find middle element of linked list in one pass? (solution)
• How to solve the Producer-Consumer Problem in Java. (solution)
• How to search element in an array in Java? (solution)
• How to sort an array using bubble sort algorithm? (algorithm)
• How to calculate Sum of Digits of a number in Java? (Solution)
• Write a Program to Check if a number is Power of Two or not? (program)

Thanks for reading this coding interview question so far. If you like this String interview question then please share with your friends and colleagues. If you have any question or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.