0

所以我做了一个阿特金算法的筛子来生成素数（针对欧拉计划问题）。它返回一个名为 的素数 (int[]) 数组primes。问题是，每当我尝试从某个索引访问该数组时（我在我的main方法中这样做），它都会抛出一个java.lang.ArrayIndexOutOfBounds异常。请帮忙（如果您认为我的逻辑与仙女不符，并且有更简单的方法可以做到这一点，请告诉我）！

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

2 回答 2

2

没有“索引无效的数组”之类的东西。如果您正在访问数组并且得到一个ArrayIndexOutOfBounds，那么要么您使用的是负索引，要么数组没有您想象的那么大。调试您的代码以找出数组的实际长度（使用array.length）并将其与您的预期进行比较。

编辑：好的，现在我们有了代码，我们可以看到问题所在。当您计算出数组的大小时，您并没有计算值 2 和 3 - 但您在填写primes. 因此primes两个值太短了。

您可以通过设置isPrime[2]和isPrime[3]来解决此问题true。然后，您不需要之前的检查limit > 2etc - 只需遍历整个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;
    }
}
于 2012-06-25T19:19:36.553 回答
1

您的问题是您将 1 标记为素数，而不是 isPrime 数组中的 2 和 3，因此当您计算素数时，您的计数会减一。然后，当您开始填充素数数组时，您不会检查素数 2 和 3 的 isPrimes 数组，而是假设它们已被正确计算并在您的素数数组中标记它们，然后开始添加其余素数（现在是一个太多了）。

如果您在循环中添加一些调试，您可以在其中计算素数并填充素数数组，您应该很容易找到它。

于 2012-06-25T20:03:34.370 回答