-3

https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/

// 一个优化的基于学校方法的 C++ 程序来检查 // 如果一个数字是素数

#include <bits/stdc++.h> 
using namespace std; 

bool isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 

    // This is checked so that we can skip  
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 

    return true; 
}
4

2 回答 2

0

任何复合数都至少有一个因子小于或等于其平方根。为什么？因为如果它只有一个因子（除了它自己或一个），那将等于它的平方根。如果它有两个或更多，最小的一个必须小于它的平方根。所以不需要检查大于平方根的数字——如果它不是素数，我们已经找到了一个因子。

代码会提前检查 2 或 3 作为一个因素。之后，我们只需要检查不是 2 或 3 的倍数的因子。所以在我们检查了 5 和 7 之后，我们不需要检查 6、8、9 或 10。所以在每六个数字中，我们只需要检查两个不是 2 或 3 的倍数的数字。

于 2019-03-05T19:49:33.333 回答
0

当您搜索质数时，您可以遍历 2 和您的数字之间的所有数字，以查看它们是否划分为您的数字。

for (int i=2; i < n; i=i+1) 
    if (n%i == 0)
       return false;

但这会检查很多您不需要的数字。
第一个观察结果（优化）是任何 2 的倍数（偶数）已经通过简单地除以 2 检查一次来检查。

所以现在我们检查 2，然后跳过每个其他偶数字符。

if (n%2 == 0 ) return false;

for (int i=3; i < n; i=i+2) 
    if (n%i == 0)
       return false;

下一个观察结果（优化）是您可以为三个人做几乎相同的事情。所以第一个测试涵盖了 2 和 3 的所有组合。现在在循环中，您每 6 个数字 (2*3) 跳过一次，并进行一些测试以覆盖所有不是 2 或 3 倍数的数字。

if (n%2 == 0 || n%3 == 0) return false; 

for (int i=5; i<n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
       return false;

所以这只是一种优化，意味着您不必尝试每个数字。

我们做出的下一个观察是，您不需要尝试大于 n 的平方根的数字（这些永远不会除以 n）。因此，您可以将循环限制为i*i < nas i*iis faster than sqrt(n).

if (n%2 == 0 || n%3 == 0) return false; 

for (int i=5; i*i<=n; i=i+6) 
    if (n%i == 0 || n%(i+2) == 0) 
       return false;

虽然我个人会做sqrt()一次而不是i*i每次循环。但对于较小的值，这可能会更慢n。

于 2019-03-05T20:05:19.020 回答