java - 寻找第 10001 个质数

Question

我正在研究 Project Euler #7 并且编写了代码:

public class Seven {

    public static void main(String[] args) {

        int i = 0;
        int c = 1;

        while (c <= 10001) {

            if (squareRootIsPrime(i)) {
                c++;
            }

            i++;

        }

        System.out.println(Math.sqrt(i));
    }

    public static boolean squareRootIsPrime (int n) {

        int x = 0;

        for (int d = 1; d <= n; d++) {
            if (n % d == 0) {x += 1;}
        }

        if (x == 3) {
            return true;
        } else {
            return false;
        }

    }

}

因为有 3 个因数的数的平方根是素数。 到目前为止，我的代码看起来是正确的，但是 Eclipse 不会打印任何内容并终止程序，那么我的代码有什么问题吗？

Answer 1

第 10001 个素数的平方略低于 110 亿。 int 可以容纳的最大值刚刚超过 20 亿。因此变量i在到达第10001个质数的平方之前就会溢出。因为发生这种情况，您将永远看不到第 10001 个素数。

理论上，如果您将变量i 和参数n 的类型更改为long，这就会起作用。但如果您这样做，您将留下必须计算大约 60 quintillion % 运算的代码(即带有 19 个零的 6)。除非你有一台速度极快的计算机，否则这在你的一生中都不会完成。

您可能需要考虑可以使用哪些其他算法。