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

Your code link doesn't go to any Java code. Please include a short but *complete* program here, within the question. — Jon Skeet, Jun 25 '12 at 19:18
Note that the code you've given doesn't compile, either. Why not just use the command line arguments? Change the first line to `int limit = Integer.parseInt(stuff[0]);` and get rid of your `getInt` method. — Jon Skeet, Jun 25 '12 at 19:55
I tried that, and it gives me another arrayindexoutofbounds exception. How do I set stuff[0] to be my number? — Bluefire, Jun 25 '12 at 20:09
Never mind, [I got it](http://stackoverflow.com/questions/890966/what-is-string-args-in-java). — Bluefire, Jun 26 '12 at 07:12

Jon Skeet · Accepted Answer · 2012-06-25T19:54:10.560

2

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

edited Jun 25 '12 at 19:54

answered Jun 25 '12 at 19:19

Jon Skeet

1,421,763
867
9,128
9,194

Ok, I uploaded the code. I got my program to tell me the size of the `count` variable, aka the length of the array, which is 24. So I have no idea why it's giving me an invalid index, *especially* if the loop that accesses it is `for(int i = 0; i < p.length; i++)` (p is my array). – Bluefire Jun 25 '12 at 19:34
You could try switching that statement over to for(int prime : p) System.out.println(prime); in the loop. That would guarantee that it would only print the valid references. – WLPhoenix Jun 25 '12 at 19:48
@Bluefire: That's not the part that's throwing the exception. You need to pay attention to the stack trace. See my edit for what's going wrong. – Jon Skeet Jun 25 '12 at 19:54
Alright, thanks! After a few twists here and there, it works perfectly! – Bluefire Jun 25 '12 at 20:07

score 1 · Answer 2 · answered Jun 25 '12 at 20:03

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.

Sieve of Atkin returns array... with invalid indices - Java

2 Answers2