How to generate Prime numbers in Java? Sieve of Eratosthenes Algorithm Example (original) (raw)
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.