为什么迭代每次都由 i+6 完成，为什么这个质数测试函数的条件是 i*i<=n？

Question

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; 
}

Answer 1

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

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

Answer 2

当您搜索质数时，您可以遍历 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 < n，因为 i*i 比 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.

的小值，这可能会更慢

为什么迭代每次都由 i+6 完成，为什么这个质数测试函数的条件是 i*i<=n？

why the iteration is done by i+6 every time and why the condition is i*i<=n for this prime testing function?

c++

primality-test