为什么 isPrime using i*i < n return 对除 2^31- 1 之外的每个 int 都是正确答案

Question

考虑这段代码：

public static boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
    return n > 1;
}

public static int squareOf(int n) {
    int i = 0;
    while (i * i < n)
    i++;

    return i * i == n ? i: -1;
}

因为 (46340)(46340)< Integer.MAX_VALUE < (46341)(46341), i*i 溢出.

那么我期望的是，对于大于 (46340)*(46340) 的数字，isPrime 要么不会终止，要么最终停止但会给出一些随机答案。

每一个 int < Integer.MAX_VALUE 都会给出正确答案！！对于 Integer.Max_value 它给出了一个错误的。

为什么会发生这种情况？

在 squareOf 中，我们有 i * i < n ，而不是 i * i <= n:

对于范围 [(46 340)^2 + 1 , 2147483641]：它是正确的，除了：{2147402577, 2147465721, 2147469348, 2147478505, 2147481513, 2147481513, 2147482825, 2147482929, 2147483280, 2147483536, 2147483556, 2147483609, 2147483620, 32141}[8][8]

[2147483642 , Integer.MAX_VALUE]: 好像没有终止。

为什么它给出了很多值的正确答案？

它给出错误答案的值有什么特别之处？

为什么 对于 2147483641 之后的值不终止？

Answer 1

好吧，当 n == Integer.MAX_VALUE 循环直到 i == n 才终止，此时 n % i 是 0，而你错误地 return false.

i 迭代直到达到 n 的值（当 n==Integer.MAX_VALUE 时）的原因是 i * i 永远不会大于 Integer.MAX_VALUE, 所以循环永远不会终止，除非你通过 returning false.

来打破它

Answer 2

问题好像是这样的：

理解：循环条件 i*i <= n 对其有意义的最后一个整数 n 是 2147395600。对于 n=2147395600，循环在 i = 46340 时终止。对于 [2147395601, 2147483647] 之间的所有整数] 当 i 达到 36340 时，值 i*i <= n 为真，因此将继续到 i=34341，此时 i*i 溢出，因此不再合理。

不明白：那么为什么 isPrime 函数可以正确区分区间 [2147395601, 2147483647] 内的 88047 个整数中的素数和合数，循环终止条件不再适用？

首先，重要的是要了解在循环达到 i=46340 之前，可疑区间中的每个合数都已被识别。因此，只有对于 n 的素数，循环才会走那么远。现在剩下的问题是为什么函数几乎总是正确地将区间中的 4085 个素数识别为素数。答案也相对简单。当 i*i 溢出时（即当 i*i 在数学上大于 Integer.MAX_VALUE 时）的结果 i*i 相当于取 i*i 和 [= 的低 32 位43=] 他们变成了一个int。但是，计算 n%i 永远不会溢出，因此循环永远不会通过该条件退出（因为 n 必须是质数）。因此循环只会因为i*i大于n且正确returntrue而退出，否则根本不会退出而成为无限循环。

我们现在必须说明循环退出的原因，以及上面对 n=Integer.MAX_VALUE 的分析出了什么问题。我们需要循环退出的是 i ，其中 i*i 以这样的方式溢出，即方块的低位 32 位的第 32 位等于零，其余 31 位形成一个整数大于 n。这是一个相当狭窄的范围。幸运的是，恰好有 i 的值，i*i 的溢出正好在该范围内，从而允许循环退出。值 i=593968971 将适用于所有值，您可以自己测试一下。区间内2147483629以下的所有素数都有较小的值，可以通过实验找到。

Integer.MAX_VALUE 是上述语句的一个例外。原因也很简单。没有大于 Integer.MAX_VALUE 的正整数，因此循环永远不会通过 i*i > n 退出。但是，当 i 最终命中 Integer.MAX_VALUE 时，循环将退出并且函数将 return false 因为 n%i 等于 n%n，它始终为 0。

为什么 isPrime using i*i < n return 对除 2^31- 1 之外的每个 int 都是正确答案

Why does isPrime using i*i < n return a correct answer for every int except 2^31- 1

java

int

primes

integer-overflow

mod