欧拉筛需要用当前遍历到的 i 和当前筛出的质数 prime_j 标记合数，因为 i\times prime_j 一定是合数，先进行标记，然后，最重要的优化来了：如果 i\bmod prime_j = 0，说明 i 的最小质因数为 prime_j，此时应该停止标记。
欧拉筛的时间复杂度为 O(n)。
bool is_prime[N];//is_prime[i] 用来标记 i 是不是质数
int prime[N], tot;//tot 表示当前质数的个数，prime[i] 表示第 i 个质数
void sieve_primes(int n)
{
for(int i = 1;i <= n;i ++) is_prime[i] = true;//初始化
is_prime[1] = false;//1 不是质数
for(int i = 2;i <= n;i ++)
{
if(is_prime[i] == true) prime[++ tot] = i;//如果第 i 个数是质数，把它加入 prime 数组
for(int j = 1;j <= tot && prime[j] * i <= n;j ++)
{
is_prime[prime[j] * i] = false;//标记
if(i % prime[j] == 0) break;//当 prime[j] 是 i 的最小质因数是，停止标记
}
}
}
整除与同余
整除
设 a 是非零整数，b 是整数。若存在一个整数 x，使得 b = a\times x，那么称 b 可被 a整除 或 a 可以 整除b，记作 a\mid b，也可以说 b 是 a 的倍数或 a 是 b 的因数。例如 2 \mid 6,4\mid 8。
整除具有以下性质：
性质 1：如果 a\mid b 并且 b\mid c，那么 a\mid c
性质 2：a\mid b 并且 b\mid c 等价于 a\mid (b\times x + c\times y)
性质 3：设 m\ne 0，那么 a\mid b 等价于 (m\times a)\mid (m\times b)
性质 4：设整数 x 和 y 满足 a\times x + b\times y = 1，且 a\mid n,b\mid n，那么 a\times b\mid n
证明：
根据性质 3 可得 a\times b\mid b\times n 且 a\times b\mid a\times n
再根据性质 2 可得 a\times b\mid a\times n\times x + b\times n\times y
其中 a\times n\times x + b\times n\times y = n\times(a\times x + b\times y) = n\times 1 = n，所以 a\times b\mid n
性质 5：若 b = q\times d + c，那么 d\mid b 的充要条件是 d\mid c
同余
若 a,b 为两个整数，且他们的差 a - b 能被某个自然数 p 整除，则称 a 和 b 关于模 p 同余，记作 a\equiv b \pmod p，意味着 a - b = p \times k（k 为某个整数）。例如 36\equiv 1 \pmod 5，此时 36 - 1 = 35 = 5\times 7。
对于整数 a,b,c 和自然数 n,m，对模 m 同余具有以下性质：
自反性：a\equiv a \pmod m
对称性：若 a\equiv b \pmod m，则 b\equiv a \pmod m
传递性：若 a\equiv b \pmod m,b\equiv c \pmod m，则 a\equiv c \pmod m
同加性：若 a\equiv b \pmod m，则 a + n\equiv b + n \pmod m
同乘性：若 a\equiv b \pmod m，则 a \times n\equiv b \times n \pmod m。若 a\equiv b \pmod m,c\equiv d \pmod m，则 a\times c\equiv b\times d \pmod m
同幂性：若 a\equiv b \pmod m，则 a^n \equiv b^n \pmod m
要注意的是，同余不满足同除性，即不满足 a\div n\equiv b\div n \pmod m。
若 x\ge y，设 x = q\times y + r，其中 0\le r < y，显然 r = x\bmod y。对于 x,y 的任意公约数d，因为 d\mid x,d\mid q\times y，所以 d\mid (x - q\times y)，即为 d\mid r，因此 d 为 y, r 的公约数。
辗转相除法的流程如下：
若 y = 0，则说明答案为 x。
若 y\ne 0，则根据 \gcd(x, y) = \gcd(y, x\bmod y) 往下递归。
时间复杂度 O(\log \max(x,y))。
int gcd(int x, int y)
{
if(y == 0) return x;//y = 0 则返回答案
return gcd(y, x % y);//否则继续递归
}
最小公倍数
最小公倍数指两个整数 a,b 公有的倍数中最小的数，记作 \text{lcm}(a,b)。
定理：x\times y = \gcd(x, y) \times \text{lcm}(x, y)。
因为 p 是质数，那么 \varphi(p) = p - 1，这时就转化成了欧拉定理的一种情况，由于满足欧拉定理，费马小定理一定成立。
裴蜀定理
对于二元一次不定方程 a\times x + b\times y = c，有解当且仅当 \gcd(a, b)\mid c。
证明
设 d = \gcd(a, b)，显然 d\mid a, d\mid b。
则 d\mid a\times x, d\mid b\times y。
那么，要使方程成立，必须满足 d\mid c。
扩展欧几里得算法
扩展欧几里得算法是用来求解 a\times x + b\times y = \gcd(a, b) 的一种算法。
首先，根据数论中的相关定理，此方程一定有解。
因为 \gcd(a, b) = \gcd(b, a\bmod b)，所以 a\times x + b\times y = \gcd(a, b) = \gcd(b, a\bmod b) = x \times b + y\times (a\bmod b)= x\times b + y\times (a - \lfloor \frac{a}{b} \rfloor \times b) = y\times a + (x - \lfloor \frac{a}{b} \rfloor \times y)\times b。
可以根据欧几里得算法递归，当 b = 0 时，可以得出 x = 1, y = 0,。
扩展欧几里得算法流程如下：
当 b = 0 时，x = 1, y = 0。
扩展欧几里得算法时间复杂度与欧几里得算法一样，为 O(\log \max(a, b))
void exgcd(int a, int b)
{
if(b == 0)
{
x = 1, y = 0;//b = 0 时，x = 1,y = 0
return;
}
exgcd(b, a % b);//递归
int tmp = x;
x = y;
y = tmp - a / b * y;
}
逆元
若 a\times x\equiv 1\pmod p，并且 a, p 互质，则称 a 模 p 的乘法逆元为 x，记作 a^{-1}。
费马小定理求逆元
注意，当模数 p 是质数且 a\ne 0 时，才可使用费马小定理求逆元。
根据费马小定理：
a^{p - 1}\equiv 1\pmod p
因此：
a\times a^{p - 2}\equiv 1\pmod p\\
很明显，此时 a^{p - 2} 即为 a^{-1}。
使用快速幂求出 a^{p - 2}\bmod p 即可，时间复杂度 O(\log p)。
int qpow(int a, int b, int mod)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}//快速幂模板
int get_inv(int a, int p)
{
return qpow(a, p - 2, p);//求出逆元
}