**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 |