Sieve of Eratosthenes Algorithm to generate Prime numbers upto 100 in Java

There are many occasions when you need to generate all prime numbers upto a specified integer and one algorithm which is most often used to generate prime numbers is Sieve of Eratosthenes. Its an ancient greek algorithm to find all prime numbers upto 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. A prime number is a whole number which is either divisible by 1 or itself e.g. 2, 3 and 5. You can see they are not divisible to any positive whole integer. In other words, 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, we 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 are actually prime or not.

How to differentiate between an Average and a Good Programmer? http://t.co/3FiljhhNpd #java #programming

— javinpaul (@javinpaul) May 19, 2015

How Sieve of Eratosthenes Algorithm works

The Sieve of Eratosthenes algorithm is quite simple. You create an array of larger than 1 by specified integer, so that index of array represent 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 doesn't have any factor other than 1 and if a number is multiple of 2 it means it is divisble by 2, hence not prime. In order to cross all numbers which are multiple by 2, we just skip our array counter by 2, which means 2, 4, 6, 8 all are multiples of 2 and they well 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 becasue 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 its already crossed because it was multiple of 2 so we skip to next number which is 5. Again 5 is a prime number so we mark it as prime and cross out all numbers which are multiple 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 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, its enough to check until 10.

Sieve of Eratosthenes Algorithm Implementation in Java 

Here is our Java program to generate prime numbers using Sieve of Eratosthenes Algorithm

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;
    }
    
}

and here is some of unit test 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 upto a specified integer using Sieve of Eratosthenes algorithm. This is a very efficient algorithm to generate large number of prime numbers and can be used to solve complex programming problems where you need an array of prime numbers.

If you like this article and would like to try out 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 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 Palindrome or not? (program)
• Write a program to check if Array contains duplicate number or not? (Solution)
• How to find Fibonacci sequence upto a given Number? (solution)
• How to prevent Deadlock in Java? (solution)
• How to find largest prime factor of a number in Java? (solution)
• How to calculate factorial using recursion in Java? (algorithm)
• How to declare and initialize two dimensional array in Java? (solution)
• Write a program to find missing number in a sorted array? (algorithm)
• How to find largest and smallest number in array? (solution)
• How to find prime factors of an integer in Java? (solution)
• Write a function to find middle element of linked list in one pass? (solution)
• How to solve Producer Consumer Problem in Java. (solution)
• How to search element in array in Java? (solution)
• How to sort 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)