为什么我们要检查 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;
    }
}

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

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)

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

Why do we check i <= sqrt(n) to find if a number is prime or not?

primes

primality-test