How to generate 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 numbers 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 the Sieve of Eratosthenes Algorithm. Surprisingly, not many developers know about this algorithm, particularly Java programmers, which is mainly because of 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 that 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 on the fundamentals. It's both comprehensive and affordable as I bought this course for just $11 on the Udemy flash sale.

How Sieve of Eratosthenes Algorithm works? Explanation

The Sieve of Eratosthenes algorithm is quite simple. You create an array 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. The next number in the array is 3, now 3 is also not divisible by anyone so it's 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 the array counter by 3, which means 3, 9, 12, 15 all are crossed. Now, the 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 the array counter by 5, so numbers like 10, 15, 20, 25 will be crossed out.

We continue this process until we reach 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.

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 unit tests to check whether our program is working properly or not. Unit tests are really important and I highly recommend you to write a Unit test whenever you write code that has some logic like this one. 

If you struggle to write unit tests in Java then I suggest you join a hands-on unit testing course like Learn Java Unit Testing with Junit & Mockito in 30 Steps by Ranga Karnam on In28Minutes on Udemy. It's a nice course to learn both JUnit and Mockito to write unit tests in Java. 

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 the 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.

Other Java Coding Problems for Practice
If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at the 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 the 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 the 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's number or not? (solution)
• Write a Program to 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 do find the largest and smallest number in an array? (solution)
• Write a function to find the middle element of the linked list in one pass? (solution)
• How to solve the Producer-Consumer Problem in Java. (solution)
• How to search an element in an array in Java? (solution)
• How to sort an array using the 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 array interview question then please share it with your friends and colleagues. If you have any questions 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.

And lastly one question for you? which one is your favorite Java program from school or college days? prime numbers, finding missing element in array? sorting algorithms, palindrome, or anything else?