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

}