# Optimization of a basic Sieve of Eratosthenes algorithm

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]) {
}
}

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.

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.