java - BitSet(JAVA) 在埃拉托斯特尼筛法的实现中抛出 outofBoundsException

Question

这是我实现埃拉托斯特尼筛法的函数，

void solve() throws IOException {

    int n = 200000;

    ArrayList<Integer> primes = new ArrayList<Integer>();
    BitSet bs = new BitSet(n + 1);

    for(int i = 0; i <= n + 1; i++)
        bs.set(i);

    //setting bits at 0 and 1 to 0, since these are not considered as primes
    bs.clear(0);
    bs.clear(1);

    for(int i = 2; i <= n + 1; i++) {
        if(bs.get(i)) {
            //cross out multiples of i starting from i*i (lesser one would have always been crossed out)
            for(int j = i*i; j <= n + 1; j += i)
                {
                    bs.clear(j);
                }

            primes.add(i);          //add this prime to the list

        }
    }

    for(int e : primes)
        out.println(e);
}

当我运行这个程序时，我在内部 for 循环期间得到 arrayOutOfBoundsException，即

for(int j = i*i; j <= n + 1; j += i)
{
  bs.clear(j);            //EXCEPTION is raised here
}

我收到的错误消息是:

Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -2146737495
at java.util.BitSet.clear(BitSet.java:532)
at ERATOSTHENES.solve(ERATOSTHENES.java:45)

我不明白问题出在哪里，如果我将 n 减少到 20000，那么我的代码可以正常工作，但是在 n = 168000(大约)之后，它会显示此 OutofBoundsException。

它是 BitSet 特有的东西吗？我没有得到一些属性？

Answer 1

您正在将变量 i 初始化(在最坏的情况下)为接近 200,000 的大数(特别是大素数？)。这意味着初始化为 i * i 的 j 将超过 40,000,000,000，这大大超过了 int 的最大值(大约 2,147,000,000)这意味着它们将溢出到负值，这肯定会超出范围。

要解决这种情况下的问题，请将变量声明为 long 类型，它是 64 位并且可以容纳更大的值。