为什么检查i <= sqrt（n）来确定数字是否为质数？ [重复]

Question

此问题已经在这里有了答案：

Why do we check up to the square root of a prime number to determine if it is prime?（13个回答）

[<13小时前关闭。

我知道这个问题之前已经回答过，但是我不太理解该问题的解释。

我在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)