0

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

我在 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循环中使用？

4

1 回答 1

2

假设n是一个合数。

然后，n = abwherea和bboth 在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)

于 2019-12-22T01:53:48.897 回答