java - 为什么我们在寻找素数时可以使用 sqrt(n) 而不是 n/2 作为上限?

标签 java algorithm math

<分区>

我们如何在这段代码中使用 sqrt(n) 而不是 n/2?使用 sqrt(n) 是否正确?

    static boolean isPrime(long n)
{
    if(n<=1) return false;
    double limit = Math.sqrt(n);
    for(long i = 2; i <= limit; i++)
    {
        if(n%i==0) return false;
    }
    return true;
}

最佳答案

如果 n 不是质数,比如 n = p * q,则 pq 不能都大于 sqrt(n)(否则 p*q 将大于 n)

关于java - 为什么我们在寻找素数时可以使用 sqrt(n) 而不是 n/2 作为上限?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21383349/

相关文章:

Scala 类型错误

c++ - 如何检查和处理非常接近于零的数字

一旦按下按钮,Java 键事件就不会执行

java - Spring 3.1 Java 配置和内部 bean

java - 如何通过SAX获取嵌套xml对象的数据

Java 无符号除法不强制转换为长?

java - 查找数组中的最小值和最大值

python - 如果我将女王的攻击范围限制在 5 个方格,我如何检测女王是否安全?

尝试查找下一个最大值时出现 Python 算法错误

c++ - 基于不同坐标系旋转图像