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.