Sieve of Eratosthenes in Java Here you can find my implementation of sieve of Eratosthenes in Java.

/**
 * Return an array of prime numbers up to upperLimit
 * using sieve of Erastosthenes.
 * @param upperLimit
 * @return array of prime numbers up to upperLimit
 */
public static int[] sieve(int upperLimit) {
    // for corner cases
    if (upperLimit &lt; 2) {
        return new int[0];
    }

    if (upperLimit == 2) {
        int[] result = {2};
        return result;
    }
    //--

    int arrLength = ((upperLimit - 3) / 2) + 1;

    // This arrray will be used to perform the sieve
    int[] temp = new int[arrLength];

    // Counter for number of primes encountered
    int numPrimes = 1; // because of 2

    // populate temp array with with 3,5,7,...,upperLimit
    for(int i=3; i &lt;= upperLimit; i=i+2) {
        temp[(i-3) / 2] = i;
    }

    // Perform sieve
    for(int i=0; i &lt; arrLength; i++ ) {
        int num = temp[i];
        if (num == 0) continue;
        numPrimes++;
        for (int k = i+num; k &lt; arrLength; k=k+num) {
            temp[k] = 0;
        }
    }

    // Create result array
    int[] result = new int[numPrimes];
    result[0] = 2;
    int currentIndex = 1;

    for(int i: temp) {
        if (i!=0) result[currentIndex++] = i;
    }

    return result;
}


How does it look?
A few notes:

Right now you are using int[]s to represent the sieve.  However, the int data type is internally stored as 32-bits, which is a waste of space.

Use java.util.BitSet to represent the sieve. It provides a vector of bits that grows as needed. All bits start out as 0, and we can set and clear a bit at any index. It uses only one bit per entry. This requires slightly more computation per access for address computation and bit manipulation, but is much more compact, and utilizes the data cache more efficiently. For larger ranges of integers, we expect memory access time to dominate computation time, making this the ideal solution to represent the sieve.



To save additional space and time, at the cost of some additional complexity, we can choose not to represent even integers in our sieve (since they are divisible by 2). Instead, the element at index k will indicate the primarily of the number 2k + 3. We abstract this complexity away by wrapping BitSet in a class exposing special indexer methods.



Right now you are using i = i + 2, which could be simplified to i += 2.



Final code:

import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

public class Sieve
{
    private BitSet sieve;

    public Sieve(int size)
    {
        sieve = new BitSet((size + 1) / 2);
    }

    public boolean isComposite(int k)
    {
        assert k &gt;= 3 &amp;&amp; (k % 2) == 1;
        return sieve.get((k - 3) / 2);
    }

    public void setComposite(int k)
    {
        assert k &gt;= 3 &amp;&amp; (k % 2) == 1;
        sieve.set((k - 3) / 2);
    }

    public static List&lt;Integer&gt; sieveOfEratosthenes(int max)
    {
        Sieve sieve = new Sieve(max + 1); // +1 to include max itself
        for (int i = 3; i * i &lt;= max; i += 2)
        {
            if (sieve.isComposite(i)) continue;

            // We increment by 2*i to skip even multiples of i
            for (int multiplei = i * i; multiplei &lt;= max; multiplei += 2 * i)
                sieve.setComposite(multiplei);
        }

        List&lt;Integer&gt; primes = new ArrayList&lt;Integer&gt;();
        primes.add(2);
        for (int i = 3; i &lt;= max; i += 2)
            if (!sieve.isComposite(i)) primes.add(i);
        return primes;
    }
}