方法三：用线性筛（欧拉筛），对所有的数先扫一遍，当扫到第 i 个数时如果这个数先前未被标记则保存到素数表中，然后筛掉当前的素数表中的每一个数与这个数的乘机和这个数的平方，如果已被标记则直接跳过并筛掉部分它的倍数，具体筛掉那些见下面的代码（注：此代码源自 oi-wiki）。
由于所有合数只被标记了一遍，所以时间复杂度为 O(n)。
vector<int> pri;
bool not_prime[N];
void pre(int n) {
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
}
for (int pri_j : pri) {
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
// i % pri_j == 0
// 换言之，i 之前被 pri_j 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
// pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
// 掉就好了
break;
}
}
}
}
方法二和方法三的两种筛法用于求所有的（或多个）质数。
Part 3.同余
当整数 a 和整数 b 除以整数 m 的余数为同一个数是 a \equiv b \pmod m ，或者说，若 m 是正整数，a，b是整数，且 m|(a-b) 或 (a-b)\%m=0,则称 a 和 b 模 m 同余。
把同余当作一种运算，是因为同余满足运算的诸多性质：
它满足自反性（一个数永远和自己同余）。
对称性（a 和 b 同余，b 和 a 也就同余）。
传递性（a 和 b 同余，b 和 c 同余可以推出 a 和 c 同余）。
一些定理和性质：
若 a \equiv b \pmod m 且 d|m，则 a \equiv b \pmod d。
如果 a \equiv b \pmod m 且有 c \equiv d \pmod m 那么下面的模运算律成立：a+c \equiv b+d \pmod m，a-c \equiv b-d \pmod m，a \times c \equiv b \times d \pmod m。
如果 a \times c \equiv b \times d \pmod m 且 c 与 m 互质，则 a \equiv b \pmod m。
Part 4.快速幂
对于快速计算 a^b \bmod c 这个式子大家应该都学过二分快速幂，但是我们也都知道位运算是一个非常快的运算符，所以理论上可以用位运算来求这个式子（注：a，b 和 c 均为正数）。
但有的时候它太快了，甚至超出了 long long 的数据范围，需要慢一点。
以上这两种快速幂的方法个人不太建议使用，多数时候都建议写二分快速幂。
位运算快速幂代码如下：
int quick_pow(int a,int b,int mod){
int ans=0;
while(b){
if(b&1)ans=(ans+a)%mod;
b=b>>1;
a=(a<<1)%mod;
}
return ans;
}
慢的快速幂代码如下：
int mul(int a,int b,int mod){
int ans=0;
while(b){
if(b&1) ans=(ans+a)%mod;
b>>=1;
a=(a<<1)%mod;
}
return ans;
}
int fst(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=mul(ans,a,p);
a=mul(a,a,p);
b>>=1;
}
return ans;
}