/*
 *  Following implementation of sieve of eratosthenes returns a boolean array which contains true is its index is prime
 *  less than or equal to a number n.
 *  Space complexity : O(n).
 *  Time complexity : O(n).
 */

public class SieveOfEratosthenes {

    public static boolean[] sieveOfEratosthenes(int n) {
        int sqrtOfn = (int)Math.sqrt(n) + 1;
        boolean[] primes = new boolean[n + 1];
        for (int i = 2; i < n + 1; ++i) {
            primes[i] = true;
        }
        for (int i = 2; i <= sqrtOfn; ++i) {
            if (primes[i]) {
                for (int j = 2 * i; j < n + 1; j += i) {
                    primes[j] = false;
                }
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 100;
        boolean[] primes = sieveOfEratosthenes(n);
        for (int i = 2; i < n + 1; ++i) {
            if (primes[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

import java.util.Arrays;

/**
 * <p>This class represents a Sieve of Eratosthenes. It exposes an isPrime(int) method.</p>
 *
 * <p>When creating a Sieve, you need to specify the max number that you might query.</p>
 *
 * <p>Time complexity for creating the Sieve is O(n * n) but for querying is O(1). Space complexity is O(n)</p>
 *
 * @see <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
 */
public class SieveOfEratosthenes {

    private boolean[] sieve;

    /**
     * Creates a sieve that can be queried for numbers up to maxNumber.
     *
     * @param maxNumber
     */
    public SieveOfEratosthenes(final int maxNumber) {
        initSieve(maxNumber);
        crossMultiplesOfKnownPrimes();
    }

    private void initSieve(int maxNumber) {
        this.sieve = new boolean[maxNumber + 1];
        Arrays.fill(sieve, true);
        cross(0);
        cross(1);
    }

    /**
     * Iterates the sieve and when it finds a prime in it, it'll cross its multiples, since by definition those numbers are not prime.
     */
    private void crossMultiplesOfKnownPrimes() {
        for (int n = 2; n * n < sieve.length; ++n) {
            if (isPrime(n)) {
                crossMultiplesOf(n);
            }
        }
    }

    /**
     * Given prime, crosses all multiples of prime in the sieve
     *
     * @param prime
     */
    private void crossMultiplesOf(final int prime) {
        for (int n = prime * prime; n < sieve.length; n += prime) {
            cross(n);
        }
    }

    /**
     * Marks n as a non-prime in the sieve.
     *
     * @param n
     */
    private void cross(final int n) {
        sieve[n] = false;
    }

    /**
     * Returns true if n is a prime number, false otherwise.
     *
     * @param n
     * @return
     */
    public boolean isPrime(final int n) {
        return sieve[n];
    }

    public static void main(String[] args) {
        int max = 100;
        SieveOfEratosthenes sieve = new SieveOfEratosthenes(max);
        for (int n = 0; n < 100; ++n) {
            if (sieve.isPrime(n)) {
                System.out.println(n);
            }
        }
    }
}

Fix #586: Make Sieve Of Erathosthenes object oriented [Java] (#589)