素数检查循环为何用Math.sqrt设上限？大于平方根的数能否整除n？

function isPrime(n)
{
    if (n < 2)
        return false;

    let max = sqrt(n);

    for(let i = 2; i <= max; i++)
    {
        if (n % i === 0)
            return false;
    }

    return true;
}

核心逻辑：因数的对称性 #

如果n不是素数，必然可以分解为两个正整数的乘积：n = a × b。这时候a和b中，一定有一个数小于等于√n，另一个大于等于√n。

举个例子：n=12，√12≈3.464，它的因数对是(2,6)、(3,4)，其中2、3都≤3.464，对应的6、4都≥3.464。如果在≤√n的范围内找不到能整除n的数，那大于√n的范围内也不可能存在这样的数——因为如果有一个大于√n的因数b，那对应的a = n/b必然小于√n，早就被循环检查到了。

大数同样适用这个规律 #

不管n是几千级还是更大的数，这个结论都成立。比如n=9999，√9999≈99.995，它的因数对(99,101)里，99≤99.995，101≥99.995。如果循环到99都没找到能整除9999的数，那101及更大的数肯定也无法整除它，因为对应的另一个因数会小于99，已经被检查过了。

用√n作为循环上限，既能确保覆盖所有可能的因数，又能大幅减少循环次数，提升效率——比如检查n=1000000时，循环只需到1000，而不是999999，执行次数差了近1000倍。

内容的提问来源于stack exchange，提问作者JediCoder