Sieve of Atkin returns array… with invalid indices - Java

Question

So I made a sieve of Atkin algorithm to generate primes (for Project Euler problems). It returns an array of primes (int[]) called primes. Problem is, whenever I try accessing that array from some index (I do so in my main method), it throws me a java.lang.ArrayIndexOutOfBounds exception. Help please (and if you think my logic is away with the fairies and there is a simpler way to do this, please tell me)!

import java.lang.*;
import java.util.*;

public class SieveOfAtkin {
    public static void main(String[] stuff) {
        int limit = getInt("Limit?");
        int[] p = getPrimes(limit);
        for(int i = 0; i < p.length; i++) {
            System.out.println(p[i]);
        }
    }
    public static int[] getPrimes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        double sqrt = Math.sqrt(limit);
        int n = 0;
        for(int i = 0; i < limit + 1; i++) {
            isPrime[i] = false;
        }
        for(int x = 0; x < sqrt; x++) {
            for(int y = 0; y < sqrt; y++) {
                n = 4 * x * x + y * y;
                if(n <= limit && (n % 12 == 1 || n % 12 == 5)) {
                    isPrime[n] = !isPrime[n];
                }
                n = 3 * x * x + y * y;
                if(n <= limit && n % 12 == 7) {
                    isPrime[n] = !isPrime[n];
                }
                n = 3 * x * x - y * y;
                if(n <= limit && n % 12 == 11 && x > y) {
                    isPrime[n] = !isPrime[n];
                }
            }
        }
        for(int i = 5; i < sqrt; i++) {
            if(isPrime[i]) {
                for(int j = i * i; j < limit; j = j + (i * i)) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 0; i < isPrime.length; i++) {
            if(isPrime[i]) {
                count++;
            }
        }
        int[] primes = new int[count];
        int found = 0;
        if (limit > 2) {
            primes[found++] = 2;
        }
        if (limit > 3) {
            primes[found++] = 3;
        }
        for (int p = 5; p <= limit; p += 2) {
            if (isPrime[p]) {
                primes[found++] = p;
            }
        }
        return primes;
    }
public static int getInt(String prompt) {
    System.out.print(prompt + " ");
    int integer = input.nextInt();
    input.nextLine();
    return integer;
}
}

Answer 1

There's no such thing as an "array with invalid indices". If you're accessing the array and you're getting an ArrayIndexOutOfBounds, then either you're using a negative index or the array isn't as big as you think it is. Debug into your code to find out the actual length of the array (with array.length) and compare that with what you expected it to be.

EDIT: Okay, now we've got the code, we can see what's wrong. You're not counting values 2 and 3 when you work out how big to make the array - but you are using them when you fill in primes. Therefore primes is two values too short.

You can fix this by setting isPrime[2] and isPrime[3] to true. You then don't need your earlier checks for limit > 2 etc - just iterate over the whole of primes:

// After removing the special cases for 2 and 3 before this loop... but setting
// isPrime[2] and isPrime[3] to true
for (int p = 2; p <= limit; p++) {
    if (isPrime[p]) {
        primes[found++] = p;
    }
}

Answer 2

Your problem is that you mark 1 as a prime, but not 2 and 3 in the isPrime array so when you count the number of primes your count is off by one. Then, when you start populating your primes array you do not check the isPrimes array for primes 2 and 3 but instead assume that they have been calculated correctly and mark them in your primes array and then start adding the rest of the primes (which now are one too many).

If you add some debug to your loops where you count the number of primes and populate the primes array you should find it easily.