## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Enumerate primes up to a number N

Sharing is caring!

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 $N = 30$.
1. First generate a list of integers from 2 to 30.
2. Start with the first number in the list, $2$ (the smallest prime number): cross out every multiple of $2$ after $2$. That is, cross out $4,6,8,10,12, \dots n$
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 $\le n$.
4. Repeat step 3 for numbers $3 \dots \sqrt n$. We only need to iterate till $\sqrt n$, since for any $j \textgreater \sqrt n$ such that $j \times i = k$ for some $i$ (obviously $i \textless j$) we would already have crossed off $k$ in a previous iteration with $i$.

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);
}

}