Hey guys, I have a Java related question:
I wrote a program that calculates every prime number from 2 to N by implementing the
Sieve of Eratosthenes. It uses an ArrayList to hold the integer values:
Code:
private void sieveOfEratosthenes() {
// Start by filling an ArrayList of integers between 2 and N.
for (int i = START; i <= END; i++) {
original.add(i);
}
for (int i = 0; i < original.size(); i++) {
// Go through every number in the array, excluding the first element.
for (int j = i + 1; j < original.size(); j++) {
// Find all multiples of the " i "'th element in the array and
if (original.get(j) % original.get(i)== 0) {
// remove them.
original.remove(j);
}
}
}
Then I print out the list of prime numbers by using another for loop. The program works perfectly fine but significantly slows down if I set N to 100,000 or any number bigger than that. Is this related to a memory cap in Eclipse? Am I running out of virtual memory to hold every heap and stack value of the array? Or maybe this is exclusively related to CPU performance?
100k items shouldn't be more than some megabytes of memory, if we're talking ArrayList (pointer, 64bits, integer, 32 bits = 96*100k, we're at barely 10mb of ram)
Still, you're running a O(n^2) operation. You can expect it to slow down significantly.
Also, poking holes in ArrayLists is generally problematic. (e: Since we're there, if you expect to do a huge amount of not-at-the-end insert\remove, use LinkedList, not ArrayList)
Plus, you aren't really well implementing the Sieve.
You are basically, for every single prime, scrolling down the whole list of integers smaller than N, and checking every single one to see if it's a multiple. This is extremely inefficient.
If you were going in the other direction (and you should), you'd compile a list of the multiples of the number smaller than N (temp list, while that breaks when one item is bigger than N-number).
Multiplication is much heavier than a %== check, but not enough so to go around doing 100k checks on very high primes while you could do ~100 removals straight-out. (Even if some of those removal are misses, that is not that much of a problem.)
Also, since .remove() works on the index, it's probably more efficient to assign-to-zero instead of removing, and then clearing down the list when you're finished.
TL;DR: You're checking all numbers of the list for divisibility instead of calculating the multiples, leading to excessive amounts of divisibility checks.
As a final addition, you should put in an optimization of the Sieve, that is (do not check numbers that are bigger than the square root of N)
