题解：SP10818 FACTCG2 - Medium Factorization
fire_star_
·
·
题解
题目意思：
给定一个整数 n\ (1\le n\le 10^7)，分解质因数，用 x 隔开。
分解质因数板子题。
分解方法：
我们先用筛法筛出 1 \sim 10^7 所有的质数。
::::info[如果您不会质数筛，您可以看一下]{open}
质数筛筛法（接下来将默认有 n 个数）：
暴力枚举：
原理：从 1 到 n 依次枚举每一个数，每个数对从 2 到 \sqrt{n} 的数进行取模运算。
:::warning[这里为什么是 \sqrt{n} 而不是 n？]
:::
缺点：时间复杂度为 $\Theta(n \times \sqrt{n})$，遇到大数据会 TLE。
代码：
```cpp
bool prime(int a) { // 只会返回 0 或 1
// 特判部分
if (a == 1) return 0; // 非质数
if (a == 2) return 1; // 质数
if (a == 3) return 1; // 质数
// return 自带结束功能，不会进行下方操作
for (int i = 2; i <= sqrt(a); i++) { // 依次对 2~sqrt(a) 取模
if (a % i == 0) { // 能被非 1 和自身整除，说明是合数
return 0;// 非质数
}
}
return 1;// 检查完之后仍然没有判断为非质数，说明这个数是质数
}
```
埃氏筛法：
原理：每次检测到质数后把所有此质数的倍数由质数区转移到非质数区，最后输出所有质数区的数。
缺点：有些数可能会被转移至非质数区多次，时间复杂度为 $\Theta(n \times log_2(log_2n))$，时间复杂度较暴力枚举有所优化，但仍有更优方法。
代码：
```cpp
bool prime[n + 1];//预处理n范围内的素数，prime[i] = 1表示i是素数
void InitPrime() {
int i, j; //初始化数组
for (i = 0; i <= n; i++) prime[i] = 1; //规定0和1不是质数
prime[0] = prime[1] = 0; //筛质数
for (i = 2; i <= n; i++) { //如果i是质数
if (prime[i]) { //把i的倍数都标记为不是质数
for (j = i * 2; j <= n; j += i) prime[j] = 0;
}
}
}
```
欧拉筛法：
原理：在埃氏筛法的基础上，我们可以避免重复被转移的数，例如：
> $35$ 既被筛 $5$ 的倍数时筛掉，又被筛 $7$ 的倍数时筛掉。
此时时间复杂度为 $\Theta(n)$。
代码：
```cpp
bool prime[n + 1];//预处理n范围内的素数，prime[i] = 1表示i是素数
vector<int> p;//存放范围内所有素数 p.size() = 素数个数
void InitPrime() {
//初始化
for (int i = 0; i <= n; i++) prime[i] = 1;
prime[0] = prime[1] = 0;
p.clear();
//注意优化后的 i * i <= n 和 j = i * i 开始
for (int i = 2; i * i <= n; i++)
if (prime[i])
for (int j = i * i; j <= n; j += i) prime[j] = 0;
//也可将所有的质数存放进vector中方便使用，例如p.size() = n范围内素数的个数
for (int i = 0; i <= n; i++) {
if (prime[i]) p.push_back(i);
}
}
```
::::
然后读题，发现要在输出的最前端加上 `1x`，所以我们输出即可。
然后是分解质因数。
::::info[如果您不会分解质因数，您可以看一下]{open}
原理：用 $n$ 模刚才找到的从小到大的质数，从 $1$ 开始。用得数不断模这个数，知道不能继续整除为止。接着将模数指向下一个质数，直到它本身也变成了一个质数。
代码：
```cpp
int *factorize(int num, int len) {
int *result = (int *)malloc(len * sizeof(int));
int i = 2;
int result_idx = 0;
while (i * i <= num) {
while (num % i == 0) {
result[result_idx] = i;
num /= i;
result_idx++;
}
i++;
}
if (num > 1) {
result[result_idx] = num;
}
return result;
}
```
::::
最终代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
bool ip[10000005];
int p[1000005], t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 10000000, i, j;
ip[0] = ip[1] = true;
for (i = 2; i <= n; i++) {
if (!ip[i]) p[++t] = i;
for (j = 1; p[j]*i <= n && j <= t; j++) {
ip[i * p[j]] = true;
if (i % p[j] == 0)
break;
}
}
while (cin >> n) {
printf("1");
if (n == 1) goto next;
for (i = 1; p[i]*p[i] <= n; i++) // sqrt 是一个函数，如果使用有可能会 TLE
while (n % p[i] == 0)
n /= p[i], printf(" x %d", p[i]);
if (n > 1) printf(" x %d", n);
next:
printf("\n");
}
return 0;
}
```