基于Eratosthenes筛的Java素数计算器算法

Question

我偶然发现了以下问题：我有一个类来获取和打印1到N之间的所有素数。N是一个你必须自己插入的参数。当我为N插入10000时，代码工作并打印出从2到最接近N的素数的所有素数

当我插入40000时，代码仍然有效。当我插入50000（或更高）时，代码会给出一个ArrayOutOfBoundsException。为什么

这是我使用的代码：

  ArrayList<Integer> priemGetallen = priemGetallen(n);
        for (Integer i : priemGetallen) {
              System.out.println(i);
        }

和使用

ArrayList<Integer> priemgetallen = new ArrayList<Integer>();

for(int i = 2; i < n; i++){
    priemgetallen.add(i);
}

for (int i = 2; i < n; i++) {
    for (int j = i; j * i <= n; j++) {
      if((j*i) < priemgetallen.size()){
          priemgetallen.remove(j*i);
        }
        }
   }
   return priemgetallen;
  }

“priemgetallen.remove（j*i）”是我收到错误的地方

如果有人能告诉我为什么这不适用于所有大于40000的N，我将不胜感激

提前谢谢

Answer 1

Java int可以容纳的最大值是2147483647，因此j * i在i和j达到46341时溢出

要扩展范围，请将i、j和n的类型更改为long

见How does Java handle integer underflows and overflows and how would you check for it?

另外，您还需要将priemgetallen更改为Long的数组列表，而不是Integer