Problem: If input is given n = 20, then print all primes numbers till 20. (Prime = Number which can be divided by exactly 2 dividers i.e. only 1 & itself)
Intuitive approach: Intuitively you can just iterate from 1 to 20 & check if each number is prime or not. But that will be an expensive algorithm.
Sieve of Eratosthenes: Greek mathematician Eratosthenes provided an efficient algorithm to find such prime numbers.
- First assume all numbers from 2 till 20 are prime.
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
- Then start with 2 & mark all its multiples as not prime. (Strike-through below)
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
- Then go to next prime (Next non strike-through) i.e. 3 & mark its multiples as non-prime. (Strike-through below)
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
- Then go to next prime (Next non strike-through) i.e. 5 & mark its multiples as non-prime. (Strike-through below)
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
- Go on till there are no more next prime remaining & list is over. Remaining numbers will all be primes (Marked in blue).
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
Java Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Sieve of Eratosthenes public class FindAllPrime{ public static void main(String... args){ FindAllPrime f = new FindAllPrime(); f.printAllPrimes(100); } public void printAllPrimes(int n){ // Create boolean array. Index represents numbers // Array starts from 0, but we will count from 1, hence size n+1 boolean[] primes = new boolean[n+1]; // Mark each index to true i.e. prime = true for(int i=0; i<primes.length; i++){ primes[i]=true; } // Starting with 2, start marking multiples as prime = false for(int i=2;i<primes.length;i++){ if(primes[i] == true){ for(int j=i+i;j<primes.length;j=j+i){ primes[j]=false; } } } // Indexes which are true are prime numbers for(int i=2;i<primes.length;i++){ if(primes[i]==true){ System.out.println(i); } } } } |
Output:
|
1 2 3 4 5 6 7 8 |
2 3 5 7 11 13 17 19 |