在 java 中找到素数

Question

我遇到了以下一种查找数字是否为素数的解决方案：

//checks whether an int is prime or not.
boolean isPrime(int n) {
if (n == 2){
    return true;
}
//check if n is a multiple of 2
if (n%2==0){
    return false;
}
//if not, then just check the odds
for(int i=3;i*i<=n;i+=2) {
    if(n%i==0)
        return false;
}
return true;

}

我想理解的是这行代码：

for(int i=3;i*i<=n;i+=2)

如何

i*i<=n

帮助确定数字是素数？

谢谢

Answer 1

这是一个合乎逻辑的规则：一旦您通过了平方根，就没有必要搜索其他除数，因为此时您的 "new" 个除数将小于您的平方根。

因数成对出现：10 = 2 x 5。2 和 5 都是因数。在每一对中，一个 <= 平方根，另一个 >= 平方根。 2 <= 开方（10）； 5 >= 开方 (10)。找到 2 后，无需继续搜索 5。5 = 10 / 2.

例如：100：您检查 2、3、5、7、9，然后停止，因为如果您检查下一个 (11)，100/11 是 9，而您已经检查了 9。你停在平方根处。

Answer 2

如果你发现 n 的所有约数（包括素数）都是 a,b,c,d...h。

如果除数 h > sqrt(n) 存在，则某些除数 c 也必须存在，使得

h * c = n
and since h > sqrt(n) and h * c = sqrt(n) * sqrt(n)
c < sqrt(n).

因此，如果存在大于 sqrt(n) 的除数，则小于 sqrt(n) 的除数也必须存在，并且应该能够在循环计数超出 sqrt(n) 之前中断循环。所以，我们不需要计算超过 sqrt(n)，因此条件

i*i < n

是强加的。

在 java 中找到素数

to find a prime number in java

java

algorithm

primes