定义

$素数（质数）：在大于1的自然数中，只有1和该数本身两个因数的数$

判断方法

方法1

$时间复杂度O(n)$
$定义法$

bool isPrime(int n){if(n < 2) return false;for(int i = 2; i < n; i++) if(n % i == 0) reutrn false;return true;
} 

方法2

$时间复杂度O(\sqrt{\frac{n}{2}})$

$性质：对于合数a，一定存在素数p_1\le \sqrt{a}\le p_2使得p_1$ $|$ $a，p_2$ $|$ $a（定性理解）$
$定量证明$

$原理：检验[1,\sqrt{n}]区间里的数是否有约数，检验区间从[1,n]缩小到[1,\sqrt{n}]$

bool isPrime(int n){if(n < 2) return false;for(int i = 2; i < sqrt(n); i++) if(n % i == 0) reutrn false;return true;
} 

方法3

$在方法2的基础上，只筛奇数$
$因为除2以外的偶数都是合数，直接跳过，只关心奇数即可$

bool isPrime(int n){if(n < 2) return false;for(int i = 2; i < sqrt(n); i++) if(n % 2 == 0 || n % i == 0) reutrn false;return true;
} 

方法4

$原理：所有大于3的素数都可以表示为6n\pm 1的形式$

$证明：n\in N，n可以用6n-1(6n-1<=>6n+5)、6n、6n+1、6n+2、6n+3、6n+4表示$
$其中，6n是6的倍数，不是素数$
$6n+2是偶数，只有n=0时，6n+2=2才是素数$
$6n+3是3的倍数，只有n=0时，6n+3=3才是是质数$
$6n+4是偶数，且大于2，不是质数$
$所以，当n>0时，6n\pm 1是质数$
$证毕.$

bool isPrime(int n){if(n < 2) return false;if(n % 6 != 1 && n % 6 != 5) return false;for(int i = 5; i <= sqrt(n); i += 6) if(n % i == 0) return false;return true;
} 

方法5

埃拉托斯特尼筛法
Eratosthenes筛选

#include<bits/stdc++.h>
using namespace std;
int main(){int n, p = 0;//p:素数的个数 cin >> n;bool is_prime[n + 5];//标记是否为素数 int prime[n + 5];//prime[p]:第p位素数 for(int i = 0; i <= n; i++) is_prime[i] = true;is_prime[0] = is_prime[1] = false;for(int i = 2; i <= n; i++){if(is_prime[i] != 0){prime[p++] = i;for(int j = i + i; j <= n; j += i) is_prime[j] = false;}}return 0;
}

$优化1$
$只筛奇数$
$把2的倍数筛掉，直接让i从3开始循环每次加2$
$这样做内存需求减半，操作大约也减半$

#include<bits/stdc++.h>
using namespace std;
int main(){int n, p = 1;//p:素数的个数 cin >> n;bool is_prime[n + 5];//标记是否为素数 int prime[n + 5];//prime[p]:第p位素数 for(int i = 0; i <= n; i++) is_prime[i] = true;is_prime[0] = is_prime[1] = false;prime[1] = 2;for(int i = 3; i <= n; i += 2){if(i % 2 != 0 && is_prime[i] != 0){prime[p++] = i;for(int j = i + i; j <= n; j += i) is_prime[j] = false;}}return 0;
}

$优化2$
$假设存在x<i^2，不妨设x=a\times b(a<b)$
$如果a,b>i，那么a\times b>i^2，与假设x<i^2矛盾$
$因此，有a\le i$
$这意味着当我们循环for到i之前，就早已经将这个数x筛过$
$所以我们优化从i^2开始标记$

#include<bits/stdc++.h>
using namespace std;
int main(){int n, p = 1;//p:素数的个数 cin >> n;bool is_prime[n + 5];//标记是否为素数 int prime[n + 5];//prime[p]:第p位素数 for(int i = 0; i <= n; i++) is_prime[i] = true;is_prime[0] = is_prime[1] = false;prime[1] = 2;for(int i = 3; i <= n; i += 2){if(i % 2 != 0 && is_prime[i] != 0){prime[p++] = i;for(int j = i * i; j <= n; j += i) is_prime[j] = false;}}return 0;
}

$优化3$
vector

#include<bits/stdc++.h>
using namespace std;
int main(){int n, p = 1;//p:素数的个数 cin >> n;vector<int> prime;//prime[p]:第p位素数vector<bool> is_prime(n + 5, true);//标记是否为素数 is_prime[0] = is_prime[1] = false;prime.push_back(2);for(int i = 3; i <= n; i += 2){if(i % 2 != 0 && is_prime[i] != 0){prime.push_back(i);for(int j = i * i; j <= n; j += i) is_prime[j] = false;}}return 0;
}

$优化4$
bitset
$⚠$ $bitset的大小得是确定的$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int main(){int n, p = 1;//p:素数的个数 cin >> n;vector<int> prime;//prime[p]:第p位素数bitset<MAXN + 5> is_prime; //标记是否为素数is_prime.set();//都标记为true is_prime[0] = is_prime[1] = false;prime.push_back(2);for(int i = 3; i <= n; i += 2){if(i % 2 != 0 && is_prime[i] != 0){prime.push_back(i);for(int j = i * i; j <= n; j += i) is_prime[j] = false;}}return 0;
}

方法6

分块筛选

方法7

线性筛法
Euler 筛法
欧拉筛法

参考
https://blog.csdn.net/way_back/article/details/122760006

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;int main(){vector<int> prime(10000, 1);for(int i=2; i<100; i++){if(prime[i]){for(int j=i; i*j<10000; j++)prime[i*j] = 0;}}ifstream in("prime.txt");for(int k; in>>k && k>1 && k<10000; )cout << k << " is " << (prime[k] ? "":"not ") << "a prime." << endl;return 0;
}

bool isPrime4(int n) {bool yes = false;int num[SIZE] = { 0 };for (int i = 2; i < SIZE; i++) {if (!num[i]) {for (int j = i + i; j < SIZE; j += i) {num[j] = 1;}}}if (!num[n]) {yes = true;}return yes;
}

bool isPrime5(int n) {bool yes = false;int num[SIZE] = { 0 };if (n == 2) {yes = true;}else {for (int i = 0; i < SIZE; i++) {if (!num[i]) {for (int j = (2 * i + 3) * (2 * i + 3); j < (2 * SIZE + 3); j += 2 * (2 * i + 3)) {num[(j - 3) / 2] = 1;}}}}if ((n - 3) % 2 == 0) {if (!num[(n - 3) / 2]) {yes = true;}}return yes;
}