为什么在查找素数时可以使用sqrt(n)而不是n/2作为上限? [英] Why we can use sqrt(n) instead of n/2 as an upper bound while finding prime numbers?

问题描述

在此代码中如何使用 sqrt(n)代替 n/2 ?使用 sqrt(n)是否正确?

How we can use sqrt(n) instead of n/2 in this code? Is it correct to use 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 ，然后 p和 q 不能都大于 sqrt(n)(否则， p * q 会大于 n )

if n is not a prime, say n = p * q, then p and q cannot be both greater than sqrt(n) (otherwise p*q would be greater than n)

这篇关于为什么在查找素数时可以使用sqrt(n)而不是n/2作为上限?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！