前端之家

  1. 首页
  2. 问答

为什么使用i * i <n的isPrime对于除2 ^ 31-1之外的每个int返回正确的答案

• 问答

考虑以下代码：

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）（46341），i * i溢出。

然后我期望的是，对于大于（46340）*（46340）的数字，isPrime要么不会终止，要么最终会终止，但会给出一些随机答案。

对于每个单个

为什么会发生？

在squareOf中，我们有i * i

对于范围[（46 340）^ 2 +1，2147483641]：正确，除了：{2147402577，2147465721，2147469348， 2147478505、2147481513、2147481513、2147482825、2147482929、2147483280、2147483536、2147483556、2147483609、2147483620、2147483641}

[2147483642，Integer.MAX_VALUE]：它似乎没有终止。

为什么会为很多值给出正确答案？

关于给出错误答案的值的特殊之处是什么？

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

caozhiting 回答：为什么使用i * i <n的isPrime对于除2 ^ 31-1之外的每个int返回正确的答案

好吧，当n == Integer.MAX_VALUE循环直到i == n才终止，此时n % i为0，而您错误地返回了false。 / p>

i进行迭代直到达到n的值（当n==Integer.MAX_VALUE时）的原因是，i * i永远不能大于Integer.MAX_VALUE，因此循环永远不会终止，除非您通过返回false中断循环。

,

问题似乎如下：

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

不理解：为什么isPrime函数在区间[2147395601，2147483647]（包括该区间）（循环终止条件不再有意义）的区间中正确地区分了88047个整数中的质数和复合数？

>

首先，重要的是要了解，在循环达到i = 46340之前，已经确定了可疑区间中的每个复合数字。因此，只有对于n的质数，循环才能达到目标值。现在剩下的问题是，为什么函数几乎总是正确地将间隔中的4085个素数识别为素数。答案也相对简单。当i*i溢出时（即i*i在数学上大于i*i时，Integer.MAX_VALUE的结果等同于取i * i的低阶32位，并“填充”他们变成一个int。但是，计算n%i不会溢出，因此循环永远不会通过该条件退出（因为n必须是素数）。因此，循环只会因为i*i大于n并正确返回true而退出，否则根本不会退出而成为无限循环。

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

Integer.MAX_VALUE是上述声明的例外。原因再次很简单。没有大于Integer.MAX_VALUE的正整数，因此循环永远不会通过i*i > n退出。但是，当i最终到达Integer.MAX_VALUE时，循环将退出并且该函数将返回false，因为n％i等于n％n（始终为0）。

intinteger-overflowjavamodprimes
本文链接：https://www.f2er.com/3110164.html

大家都在问