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

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.

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;
}

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.