为什么我们要检查 i <= sqrt(n) 来判断一个数是否是质数？

Question

我知道这个问题之前已经被回答过，但我不太明白对该问题的解释。

我在 HackerRank 上做了 30 天的代码，其中一个练习是检查一个数字是否是素数。不幸的是，我自己无法做到这一点，所以我在多次尝试后检查了给定的解决方案。即使在查看了解决方案之后，我也无法理解其中一行：

// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrt(n); i += 2){
    // n is not prime if it is evenly divisible by some 'i' in this range
    if( n % i == 0 ){ 
        isPrime = false;
    }
}

为什么sqrt(n)在for循环中使用？

Answer 1

假设n是一个合数。

那么，n = ab其中a和b都在1和之间n。

如果a > sqrt(n)和b > sqrt(n)，那么这意味着ab > sqrt(n)*sqrt(n)这基本上意味着ab > n，这与假设相矛盾ab = n。

因此，其中一个因子（a或b）必须小于sqrt(n)，或者两者都等于它。所以如果n是合数，n一定有一个素因数p <= sqrt(n)