素数一个大于1的自然数除了1和它本身以外不再有其他因数的数称为素数。合数:一个大于1的自然数除了1和它本身以外还有其他因数的数称为合数。因数整数a除以整数bb≠0的商正好是整数而没有余数称b是a的因数。一、试除法一次次试看能不能被因子整除。int is_prime(int n) { //这里用in/i防止溢出如i1e6 for (int i 2;i n / i;i) { if (n % i 0) return 0; } return 1; }二、埃式筛法——接近线性OlogN素数的倍数一定是合数。找出合数剩下都是素数。#includeiostream #includevector using namespace std; const int n 1e6 10; //创建一个bool数组来标记素数 //初始时假设所有数都是素数 vector bool isPrime(n 1, true); int main() { //遍历2~sqrt(n)的所有数 for (int p 2;p n / p;p) { //如果p是素数 if (isPrime[p]) { //标记p所有的倍数为非素数 for (int i p * p;i n;i p) isPrime[i] false; } } return 0; }三、欧拉筛法——线性埃式筛有一些重复标记欧拉筛去除了这些标记。整数唯一分解定理任何大于1的正整数n都可以唯一分解为有限个质数的乘积任何合数都有他对应的一个最小质因子。只通过这个最小质因子将其标记这样就避免了重复标记。每个数都只被它的最小质因数筛去。#includeiostream #includebitset using namespace std; const int maxn 1e6 10; bitsetmaxn pri;//0为素数1为合数 int primes[maxn]; int pp 0; int main() { int N 1e6; int cnt 0; for (int i 2;i N;i) { if (!pri[i]) { primes[pp] i; pp; } for (int j i;j pp;j) { pri[primes[j] * i] 1; if (i % primes[j] 0) break; } } }