c++ - 判断一个数是否为质数 C++

Question

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

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

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

int main() {
    int T,n;
    cin>>T;
    while(T--){
    cin>>n;
    isPrime(n)?  cout << "Prime\n": cout << "Not prime\n";
    }
    return 0;
}

嘿，所以我正在编写这段代码来判断一个数是否是素数，我做了很多研究，但我无法找到这一步的工作。

在 isprime() 函数中

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

请帮我解决这个问题，感谢您的帮助

Answer 1

循环

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

可以写成:

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

为了便于理解。您检查该数字是否可以被整除:

5 7 9 11 13, etc.

如果您将这些奇数重新排列为:

5 7 9
11 13 15
17 19 21
23 25 27

等等，

您会注意到最后一列中的所有数字都是 3 的倍数。如果任何数字可以被这些整除，它们也可以被 3 整除。由于函数一开始就已经检查了数字是否可以被 3 整除，因此没有必要检查它。因此，我们需要检查数字是否只能被整除:

5 7 
11 13
17 19
23 25

等等

这些数字的模式是:

i i+2

行之间的增量为 6。您可以将其转换为:

1. 从 i = 5 开始
2. 检查数字是否可以被i整除或 i+2 .如果是，返回 false .
3. 增量i通过 6并重复。

这就是 for 的内容循环确实如此。

为什么 for 的条件是声明i*i <= n ？

那是因为一个数不能被任何大于它的平方根的数整除。如果你到达 i*i 的地步> n ，你放心n不能被 i 整除.继续任何 i 的循环大于该值不会改变条件值。当我们到达那个点时，这个数字是质数。