Prime number generator in java using Sieve of Eratosthenes algorithm

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 & itself.
  • e.g.Number 7 is prime number because 7 have two factor i.e. 1 & 7
  • e.g.Number 4 is not prime number because 4 have factors of 1, 2 & 4.
  • List of prime numbers from 0 – 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
• Sieve of Eratosthenes is a simple algorithm for finding prime numbers up to given limit.
• Sieve of Eratosthenes algorithm is based upon elimination technique.
•  The algorithm iteratively eliminates the composite numbers, which are multiple of each prime.

Algorithm – find prime numbers till given number ( 2 to number)

• Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
• Initially, let p equal 2, the smallest prime number.
• Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, … ; the p itself should not be marked).
• Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Example: Prime numbers using Sieve of Eratosthenes algorithm

• Generate the prime numbers till 30 ( from 2 to 30)

• First number in the table is 2, so eliminates all number multiple of 2.

• Second number in table is 3, so eliminates all number multiple of 3.

• Next number in table is 5, so eliminates all number multiple of 5.

The unmarked numbers in the table are prime numbers till 30: 2 3 5 7 11 13 17 19 23 29

Program: prime number generator in java using Sieve of Eratosthenes algorithm

package org.learn.arrays;

import java.util.Arrays;
import java.util.Scanner;

public class SieveEratosthenes {
	public static void generatePrimeNumbers(int maxNumber) {

		boolean[] isPrime = new boolean[maxNumber + 1];
		Arrays.fill(isPrime, true);

		int primeRange = (int) Math.sqrt(maxNumber);
		for (int number = 2; number <= primeRange; number++) {
			if (isPrime[number]) {
				for (int iEliminate = number * number; iEliminate <= maxNumber; iEliminate += number) {
					isPrime[iEliminate] = false;
				}
			}
		}
		int number = 2;
		while (number <= maxNumber) {
			if (isPrime[number]) {
				System.out.printf("%d ", number);
			}
			number++;
		}

		return;
	}

	public static void main(String[] args) {

		try (Scanner scanner = new Scanner(System.in)) {
			System.out.print("1. Enter the number:  ");
			int maxNumber = scanner.nextInt();
			System.out.printf("2. Prime numbers till %d : ", maxNumber);
			generatePrimeNumbers(maxNumber);
		}
	}
}

Output: prime numbers in java using Sieve of Eratosthenes algorithm

1. Enter the number:  30
2. Prime numbers till 30 : 2 3 5 7 11 13 17 19 23 29 

1. Enter the number:  50
2. Prime numbers till 50 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47