Optimization of a basic Sieve of Eratosthenes algorithm

Question

I have the following Sieve of Eratosthenes algorithm:

public static ArrayList<Integer> sieveOfEra(int limit) {
    int crosslimit = (int) Math.sqrt(limit);
    boolean[] sieve = new boolean[limit+1];
    ArrayList<Integer> primes = new ArrayList<Integer>(Arrays.asList(2));

    for (int n = 4; n <= limit; n += 2) {   // mark even mumbers > 2
        sieve[n] = true;
    }

    for (int n = 3; n <= crosslimit; n += 2) { 
        if (!sieve[n]) {
            for (int m = n*n; m <= limit; m += 2*n) {
                sieve[m] = true;
            }
        }
    }

    for (int i = 3; i <= limit; i += 2) {
        if (!sieve[i]) {
            primes.add(i);
        }
    }

    return primes;
}

It returns an ArrayList of all the primes up to n. It first marks the composite numbers in a boolean array, then loops through the boolean array to add unmarked indexes as prime numbers in the primes ArrayList.

I'm looking for any feedback in general, but specially for ways to optimize the algorithm.

I understand that I can get rid of marking even numbers, and even including them in the sieve, but I don't understand how it would be implemented.

Answer 1

After adding 2 to the list of primes you are wasting half of the array space for even numbers, even time for crossing them out. Disconnect the number from it's index in the sieve, like in testprime = sieve[2*i + 3]. Now you can step with a stepsize of 1 through the sieve.

If you take that one step further and add 3 to the list of primes, you will notice that all remaining primes are of the form 6i+1 or 6i+5. The cases 6i, 6i+2, 6i+4 are even; 6i+3 is divisible by 3. So you can loop in steps of 6 and check for elements 6i+1 and 6i+5 in one pass. Thus, there are only 6/6 - 3/6 - 2/6 = 1/6 numbers left to check for, meaning a sixfold speedup.