质数相关。

质数判断

一 暴力

直接从2开始循环到n,如果n可以整除某个数，那么说明n不是质数。

#include <iostream>
using namespace std;
int main()
{int n;cin >>n;for(int i = 2;i<=n;i++){if(n % i == 0){cout << "不是质数";return 0;}}cout << "是质数";return 0;
}

二 暴力+优化

如果一个数不是质数，那么，在n ^1/2内必定会有他的因数出现，所以可以缩短循环的范围

#include <iostream>
#include <cmath>
using namespace std;
int main()
{int n;cin >>n;for(int i = 2;i<=sqrt(n);i++){if(n % i == 0){cout << "不是质数";return 0;}}cout << "是质数";return 0;
}

三 根据质数的分布规律

质数有一个分布规律——大于等于5的质数一定和6的倍数相邻（5和7，11和13）。但是和6的倍数相邻的数不一定是质数，二者不是充要条件。
由此进行剪枝，达到优化的效果。

#include<iostream>
#include<cmath>
using namespace std;
int prime(int num)   //判断素数 
{// 先把 1 2 3 解决if (num == 1)return 0;if (num == 2 || num == 3)return 1;// 不和6的倍数相邻  不是质数if (num % 6 != 1 && num % 6 != 5)return 0;// 最后只剩下和6相邻的，但是其中有非质数，需要判断int tmp = sqrt(num);// 此时步长可以增加为6，缩短查询时间for (int i = 5; i <= tmp; i += 6)if (num % i == 0 || num % (i + 2) == 0)return 0;return 1;
}
int main()
{int n;cin >> n;if (prime(n)) cout << "这个数是素数" << endl;else cout << "这个数不是素数" << endl;
}

四 质数筛