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

Question

我们如何使用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;
}

Answer 1

如果n不是素,说n = p * q的话 p而q不能同时大于sqrt(n)(否则p*q会大于n)