Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)

Answer 1

Your method of finding primes, by comparing every single element of the array with every possible factor is hideously inefficient. You can improve it immensely by doing a Sieve of Eratosthenes over the entire array at once. Besides doing far fewer comparisons, it also uses addition rather than division. Division is way slower.

Answer 2

The easiest solution would be to return some member of the Collections Framework instead of an array.

Answer 3

Create an ArrayList<Integer> and then convert to an int[] at the end.

There are various 3rd party IntList (etc) classes around, but unless you're really worried about the hit of boxing a few integers, I wouldn't worry about it.

You could use Arrays.copyOf to create the new array though. You might also want to resize by doubling in size each time you need to, and then trim at the end. That would basically be mimicking the ArrayList behaviour.

Answer 4

Restructure your code. Throw out the temporary array, and instead write function that just prime-tests an integer. It will be reasonably fast, since you're only using native types. Then you can, for instance, loop and build a list of integers that are prime, before finally converting that to an array to return.

Answer 5

Are you using Java 1.5? Why not return List<Integer> and use ArrayList<Integer>? If you do need to return an int[], you can do it by converting List to int[] at the end of processing.

Answer 6

As Paul Tomblin points out, there are better algorithms.

But keeping with what you have, and assuming an object per result is too big:

You are only ever appending to the array. So, use a relatively small int[] array. When it's full use append it to a List and create a replacement. At the end copy it into a correctly sized array.

Alternatively, guess the size of the int[] array. If it is too small, replace by an int[] with a size a fraction larger than the current array size. The performance overhead of this will remain proportional to the size. (This was discussed briefly in a recent stackoverflow podcast.)

Answer 7

Now that you've got a basic sieve in place, note that the inner loop need only continue until temp[i]*temp[i] > prime.

Answer 8

ArrayList<> Sieve of Eratosthenes

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

Formula for upper bound of number of primes less than or equal to max (see wolfram.com):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}