java - 找到素数-->筛法

Question

我尝试了几次，但仍然给了我 ArrayOutOfIndex。但我想节省内存，所以我使用

boolean[]isPrime = new boolean [N/2+1];

代替

boolean[]isPrime = new boolean [N+1];

这给了我第 23 行和第 47 行的 ArrayOutOfIndex

第 23 行：

    for (int i = 3; i <= N; i=i+2) {
    isPrime[i] = true;
    }

第 47 行：

  for (int i = 3; i <= N; i=i+2) {
        if (isPrime[i]) primes++;
  ...
   }

---

Full code:

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

        if (args.length < 1) {
            System.out.println("Usage: java PrimeSieve N [-s(ilent)]");
            System.exit(0);
        }

        int N = Integer.parseInt(args[0]);

        // initially assume all odd integers are prime

        boolean[]isPrime = new boolean [N/2+1];

        isPrime[2] = true;

        for (int i = 3; i <= N; i=i+2) {
            isPrime[i] = true;
        }

        int tripCount = 0;

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 3; i * i <= N; i=i+2) {

            // if i is prime, then mark multiples of i as nonprime
        if (isPrime[i]) {
          int j = i * i;
          while (j <= N){
            tripCount++;
            isPrime[j] = false;
            j = j + 2*i;
            }
                        }
                                            }

        System.out.println("Number of times in the inner loop: " + tripCount);

        // count and display primes
        int primes = 0;
        if(N >= 2 ){
            primes = 1;
        }
        for (int i = 3; i <= N; i=i+2) {
            if (isPrime[i]) primes++;
            if (args.length == 2 && args[1].equals("-s"))
                ; // do nothing
            else
                System.out.print(i + " ");
        }
        System.out.println("The number of primes <= " + N + " is " + primes);
    }
}

Answer 1

当您将数组的大小从 更改为[N+1]时[N/2+1]，您还需要更新 for 循环的结束条件。现在你的 for 循环运行 until i=N，所以你试图做isPrime[i]when i > (N/2+1)... 所以你得到一个ArrayIndexOutOfBoundsException.

改变这个：

for (int i = 3; i <= N; i=i+2) 

对此：

for (int i = 3; i <= N/2; i=i+2) 

Answer 2

您应该使用相同的索引函数存储和访问数组：isPrime[i/2]

Answer 3

好吧，例如，如果 N=50 你isPrime 只拥有 26 个元素，并且你试图访问 3,5..47,49 处的元素（当然，这是超出范围的）

您可能想要的是在循环中使用i/2（作为index），这样您仍在迭代数字 3、5..47、49，但您使用向量的正确索引。