Sieve of Eratosthenes in Java
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;
    }
}