算术基本定理
任何一个大于 \(1\) 的正整数 \(N\) 都能唯一分解为有限个质数的乘积，可写作：
\[N = p_1^{c_1}p_2^{c_2}...p_m^{c_m} \]其中 \(c_i\) 是正整数，\(p_i\) 是质数，且满足 \(p_1<p_2<...<p_m\)。
推论：\(N\) 的正约数的集合可写作：
\[\{p_1^{b_1}p_2^{b_2}...p_m^{b_m}\} \]其中 \(b_i\) 是正整数，且满足 \(0\le b_i\le c_i\)。
\(N\) 的正约数个数为：
\[(c_1+1)\times(c_2+1)\times ...\times(c_m+1)=\prod_{i=1}^m(c_i+1) \]\(N\) 的正约数的和为：
\[(1+p_1+p_1^2+...p_1^{c_1})\times(1+p_2+p_2^2+...p_2^{c_2})\times ...\times(1+p_m+p_m^2+...p_m^{c_m})=\prod_{i=1}^m(\sum_{j=0}^{c_i}p_i^j) \]勒让德定理
\(N!\) 中质因子 \(p\) 的个数为：
\[\lfloor\frac{N}{p}\rfloor+\lfloor\frac{N}{p^2}\rfloor+...+\lfloor\frac{N}{p^{\lfloor \log_pN\rfloor}}\rfloor=\sum_{p^k\le N}\lfloor\frac{N}{p^k}\rfloor \]例题：
阶乘分解
```cpp
void solve() {
int n;
cin >> n;
sieve(n);
for (int p : primes) {
int cnt = 0;
for (int i = p; i <= n; i *= p) {
cnt += n / i; // 勒让德定理
}
cout << p << " " << cnt << "\n";
}
}
# 筛法
### 埃拉托斯特尼筛法：
筛掉质数的倍数，同一个数会被筛多遍，时间复杂度为 $O(n\log\log n)$
```cpp
vector<int> primes, v;
void sieve(int n) {
primes.clear();
v.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (v[i])
continue; // 如果被筛过
primes.push_back(i); // 剩下的为素数
for (int j = i; j * i <= n; j++) { // 筛掉其倍数
v[i * j] = 1;
}
}
}
欧拉筛/线性筛：
确保每个合数只会被其最小质因子筛过，时间复杂度为 \(O(n)\)
void sieve(int n) {
minp.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (int p : primes) {
if (i * p > n || p > minp[i])
break;
minp[i * p] = p; // 只被最小质因子筛过
}
}
}
试除法
用 \(n\) 除以从 \(1\) 到 \(\sqrt n\) 的质数，能除则除，可在此期间找出 \(n\) 在 \(1\) 到 \(\sqrt n\) 之间的质数，若 \(n\) 最后不等于 \(1\)，则剩余的数为 \(n\) 大于
\(\sqrt n\) 的唯一质数。
例题：
素数判断
void solve() {
int x, t;
cin >> x;
t = x;
vector<int> v;
for (int p : primes) { // 试除法
if (x == 1)
break;
if (x % p == 0) {
v.push_back(p);
while (x % p == 0) {
x /= p;
}
}
}
if (x != 1) {
v.push_back(x);
}
if (v[0] == t) {
cout << "isprime\n";
} else {
cout << "noprime\n";
}
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " \n"[i == v.size() - 1];
}
}