基本定义
质数，也称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
一、试除法
简单而暴力，查看\(i(2\leq i\leq N)\)是否整除\(n,\)时间复杂度为\(O(sqrt(n))，\)相对来说比较低效
bool is_prime(int n) {
if (n < 2) return false;
for(int i = 2; i <= sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
二、埃式筛法
全称埃拉托斯特尼筛法\(（Eratosthenes筛法）\)，是个和欧几里得辗转相除一样古老的算法。
合数可以表示成一个自然数和一个素数的乘积，因此我们找到一个素数后，我们要做的就是把他小于\(n\)的倍数全部标记为合数。时间复杂度为\(O(nloglogn)，\)许多合数被无意义地标记了许多次，降低了效率。
该算法实现简单，效率已经非常接近于线性，是算法竞赛中最常用的质数筛法。
int Eratosthenes(int n) {
int w = 0;
for (int i = 0; i <= n; i++) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; i++)
if (is_prime[i]) {
prime[w++] = i;
//2到i - 1的倍数我们之前筛过了，直接从i的倍数开始，提高了运行速度
for (int j = i * i; j <= n; j += i)
is_prime[j] = 0;
}
return w;
}
三、欧拉筛法
能够让所有合数只被标记一次，时间复杂度被降到\(O(n)\)。
同时，可以利用欧拉筛法顺带求出欧拉函数。
void init() {
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break; // 关键地方，保证了每个数最多被筛一次，将时间复杂度降到了线性。
vis[i * pri[j]] = 1;
if (i % pri[j]) phi[i * pri[j]] = phi[i] * (pri[j] - 1);
else { // i 之前被 pri[j] 筛过了
// i 乘上其他的质数的结果一定会被 pri[j] 的倍数筛掉，所以这里直接 break 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}