Sieve of Eratosthenes
A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself. In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
Algorithm
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the smallest prime number.
3. 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).
4. 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.
5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
Example
To find all the prime numbers less than or equal to 26, proceed as follows.
First, generate a list of integers from 2 to 30
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
17
|
18
|
19
|
20
|
The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list)
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5):
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21) are also multiples of smaller primes because 7 × 7 is greater than 30. The numbers not crossed out at this point in the list are all the prime numbers below 20:
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
Implementation in Java
import java.util.Scanner;
/** Class SieveOfEratosthenes
* @author algos.debug. **/
public class SieveOfEratosthenes {
/** Function to calculate all primes less than n **/
private static boolean[] calcPrimes(int N) {
boolean[] arr = new boolean[N + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = true;
}
for (int i = 2; i <= Math.sqrt(N); i++) {
if (arr[i]) {
for (int j = i * i; j <= N; j += i) {
arr[j] = false;
}
}
}
return arr;
}
/** Function to get all primes **/
private static void getPrimes(int N) {
boolean[] primes = calcPrimes(N);
display(primes);
}
/** Function to display all primes **/
public static void display(boolean[] primes) {
System.out.print("\nPrimes = ");
for (int i = 2; i < primes.length; i++) {
if (primes[i]) {
System.out.print(i +" ");
}
}
System.out.println();
}
/** Main function **/
public static void main (String[] args) {
try(Scanner scan = new Scanner(System.in)) {
System.out.println("== Sieve Of Eratosthenes Prime Algorithm ==");
/** Accept n **/
System.out.println("Enter the number to find the primes");
int n = scan.nextInt();
getPrimes(n);
}
}
}
Output:
== Sieve Of Eratosthenes Prime Algorithm ==
Enter number to find all primes less than the it
11
Primes = 2 3 5 7 11
