java - 请解释试用部如何进行素性测试

Question

我通过试验师遇到了这个用于测试素数的算法我完全理解这个算法

static boolean isPrime(int N) {
    if (N < 2)
        return false;
    for (int i = 2; i <= Math.sqrt(N); i++)
        if (N % i == 0)
            return false;
    return true;
}

它工作得很好。但后来我遇到了另一个同样好用的，但我不完全理解它背后的逻辑。

static boolean isPrime(int N) {
    if (N < 2)
        return false;
    for (int i = 2; i * i<N; i++)
        if (N % i == 0)
            return false;
    return true;
}

似乎i *i < N表现得像i <= Math.sqrt(N). 如果是这样，为什么？

Answer 1

顺便说一句，如果您认为代码太慢，您可以通过一些调整来加快代码速度：

static boolean isPrime(int N) {
    if (N <= 1)
        return false;
    if (N % 2 == 0)
        return N == 2;
    for (int i = 3; i <= Math.sqrt(N); i += 2)
        if (N % i == 0)
            return false;
    return true;
}

此版本对负数和可被 2 整除进行特殊测试，然后仅除以奇数：3、5、7、...（注意“+= 2”）。

Answer 2

是的，你是对的，这些是相同的，显然等式i <= Math.sqrt(N)可以重写为整数i * i <= N，如果你对第一个等式的两个部分求平方。
, iea < b等价于a * a < b * b, 对于正 a, b;