Java:尝试使用 Sieve 计算素数时出现 ArrayOutofBounds 异常

Question

我的代码编译没有错误，但在我的输出中，第 37 行出现 ArrayOutofBoundsException。除了素数计数器之外，一切正常。谁能看到我在这段代码中犯了错误吗？主计数器在我的另一个程序中工作。

import java.util.Scanner;

public class Sieve {
public static void main(String[] args) {

    //get ceiling on our prime numbers
    int N;
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the prime number ceiling: ");
    N = sc.nextInt();
    sc.close();

    //init our numbers array, where true denotes prime
    boolean[] isPrime = new boolean[N];
    isPrime[0] = false;
    for (int c = 1; c < N; c++) {
        isPrime[c] = true;

    }

    //check every number >= 2 for primality
    //first loops, checks to see is numbers are marked
    for (int i = 2; i <= N; i++) {
        if (isPrime[i-1]) {
            System.out.print(i + " ");

            //cross off all subsequent mutliples of
            //second loop, marks all multiples of number
            for (int j = i * 2; j <= N; j += i) {
                isPrime[j-1] = false;
            }
        }
    }
    //counts primes
    int primes = 0;
    for (int c = 0; c <= N; c++) {
        if (isPrime[c]); //error here
        primes++;
    }
    //prints # of primes
    System.out.println(" ");
    System.out.println("The number of primes <= " + N + " is " + primes);
}
}

Answer 1

你的for循环条件不好

for (int c = 0; c <= N; c++) {

应该是

for (int c = 0; c < N; c++) {

因为你有一个维度为 N 的数组，并且 cointng 从 0 开始。

<小时/>

for (int c = 1; c < N; c++) {
        isPrime[c] = true;

}

此代码将所有数字设置为素数。您应该做的是将每个数字设置为质数，然后将数字的每个倍数设置为非质数。

所以会像

Arrays.fill(isPrime, true);
isPrime[0] = false;
for (int x = 1, x < N; x++) {
   for (int y = x; y < N; y+=x) {
      isPrime[y] = false;
   }
}

这应该是真正的筛选算法。引用https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes