# Enumerate primes up to a number N

**Problem statement**

How would enumerate all the prime numbers up to a given range?

**Solution**

There way we are going to solve it is using a well-known approach called Sieve of Eratosthenes.

The approach is as follows:

Assume .

1. First generate a list of integers from 2 to 30.

2. Start with the first number in the list, (the smallest prime number): cross out every multiple of after . That is, cross out

3. Get the next number that is not crossed out (which is the next prime): cross out every multiple of that number that follows which is .

4. Repeat step 3 for numbers . We only need to iterate till , since for any such that for some (obviously ) we would already have crossed off in a previous iteration with .

**Full code**

public class EnumerateAllPrimesToN { public static void solve(int n) { boolean[] isPrime = new boolean[n]; for (int i = 1; i < isPrime.length; i++) { isPrime[i] = true; } for (int i=2; i < Math.sqrt(n); i++) { if (isPrime[i]) { // Remove all multiples of i. We can start with i*i, because if we have // k*i with k < i, we would already have crossed out this value in a previous // iteration. for (int j=(i*i); j < n; j = j + i) { isPrime[j] = false; } } } for (int i=2; i < isPrime.length; i++) { if (isPrime[i]) { System.out.print(i+ " "); } } } public static void main(String[] args) { solve(18); } }