题目1： 求解因子

题解1：

1）易得，当$n=a\ast b$时，$a,b$是n的因子(假设$a<b$)

• 可以发现只需枚举到即可$\sqrt{n}$，因为$a<=\sqrt{n}<=b$
• 且，我们通过$a$可以直接得到b，（$b=n/a$）
  

代码1：求解因子

#include<bits/stdc++.h>
using namespace std;typedef long long ll;void solve()
{ll n;cin>>n;vector<ll>v;for(ll i=1; i <= n / i;i++){//表明i不是n的因子if(n%i!=0) continue;//此时有i n/i两个因子//如果这两个因子相等if(i==n/i)  {v.push_back(i);}else {v.push_back(i);v.push_back(n/i);}}sort(v.begin(),v.end());for(auto &i:v){cout<<i<<' ';}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;while(_--) solve();return 0;
}

题目2：求解质因子

题解2：

0）我们可以考虑把一个数给拆分成多个质因数以及其指数数相乘得到

1）首先，我们我们可以从2开始枚举数直到$\sqrt{n}$，并且不断去除其组成（也就是去除2、3、5）

2）并且在这个做法中，我们枚举的数一定是质数因为$i$一定会被其质数给分解,

• 假设$i=4$，且$n$为偶数，那么$i=4$不会被整除,因为$n$会被$2$给消除完全偶数这个范围，$n=6、8、\mathrm{10.....}$同理

3）总结：可以把一个数看作向量，随后我们拆分其各各方向上的值，并且他们一定不会相互干扰 （因为都为质数）

代码2：

1）代码分块解析

1. 定义类型

typedef long long ll;

• typedef long long ll;：将 long long 类型定义为 ll，这样写更简洁。

---

2. solve 函数

void solve()
{ll n;cin >> n;

• ll n; cin >> n;：读取输入值 n，即我们要进行质因子分解的整数。

---

3. for 循环开始

    vector<ll> v;for(ll i=2; i <= n / i;i++){//那么i一定会被其质数给分解,假设i==4//那么i==4不会被整除,因为i会被2给消除完全//表明i不是n的质因子if(n%i!=0) continue;//此时有i这个因子,且一定为质数,因为假如i不是质数//接下来把i除干净while(n%i==0)   //还能被i整除{n/=i;}v.push_back(i);}

这个 for 循环用于寻找 n 的所有质因子。让我们逐步理解它的意义。

3.1. 循环条件：i <= n / i

• 循环范围：i 从 2 开始，到 n / i 结束。为什么循环条件是 i <= n / i 呢？
  • i 是从 2 开始的，因为 1 不是质数，所以不需要考虑。
  • 质因子的性质决定了，我们只需要查找到 sqrt(n) 这个范围，因为任何大于 sqrt(n) 的因子，都会与小于 sqrt(n) 的因子一一对应。例如，若 n = 36，其因子对是 (2, 18), (3, 12), (4, 9), (6, 6)，注意到 6 与 6 只是一个重复因子，因此只需要检查到 sqrt(n)，即可获取所有因子。

例如，对于 n = 36：

• i 从 2 遍历到 sqrt(36) = 6，检查是否为因子。

3.2. if (n % i != 0) continue;

• 这行判断 i 是否是 n 的因子。如果 i 不能整除 n，则 n % i != 0，此时跳过当前循环，进入下一个 i。

3.3. 质因子分解：while (n % i == 0) n /= i;

• 如果 i 是 n 的因子，即 n % i == 0，进入 while 循环。
• 这时，while (n % i == 0) 会一直将 i 从 n 中除尽。即将 n 中所有的 i 因子消除，直到 n 不能再被 i 整除为止。
• 例如，如果 n = 36，i = 2，那么第一次 n /= 2 后，n 变为 18；第二次 n /= 2 后，n 变为 9；然后 n % 2 != 0，退出循环。

3.4. v.push_back(i);

• 当 i 被成功地用来除去 n 中的因子时，i 就是一个质因子，加入到 v 向量中。

4. 如果n本身就是一个质数，其没有质因子，因此我们需要特判

	//n本身就是质因子if (n > 1) v.push_back(n);

• 在 for 循环之后，如果 n > 1，说明 n 本身就是一个质数。因为如果 n 被 2 到 sqrt(n) 之间的所有数都整除，那么 n 已经变成了 1。如果 n 大于 1，说明它本身就是一个质因子，应该被加入到 v 中。

5. 排序和输出

    sort(v.begin(), v.end());for (auto &i : v){cout << i << ' ';}

• sort(v.begin(), v.end());：对质因子进行排序。虽然质因子自然是递增的，但这里显式地排序以确保输出顺序。
• for (auto &i : v)：遍历 v 中存储的质因子，按顺序输出。

总结

这个代码的核心思想是通过 for 循环遍历所有可能的因子 i（从 2 到 sqrt(n)），并检查它们是否为 n 的因子。如果是，使用 while 循环将 i 从 n 中除去，直到 i 不再是因子。最终，如果 n > 1，说明 n 本身是一个质数，加入到结果中。所有的质因子被排序后输出。

这个方法的复杂度大约是 O(sqrt(n))，因为我们只检查到 sqrt(n)，且每次 n 被分解时，都可以去除一个质因子。

2)完整代码解析

#include<bits/stdc++.h>
using namespace std;typedef long long ll;void solve()
{ll n;cin>>n;vector<ll>v;for(ll i=2; i <= n / i;i++){//那么i一定会被其质数给分解,假设i==4//那么i==4不会被整除,因为i会被2给消除完全//表明i不是n的质因子if(n%i!=0) continue;//此时有i这个因子,且一定为质数,因为假如i不是质数//接下来把i除干净while(n%i==0)   //还能被i整除{n/=i;}v.push_back(i);}//判断n是否本身就是质数if(n>1) v.push_back(n);sort(v.begin(),v.end());for(auto &i:v){cout<<i<<' ';}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;while(_--) solve();return 0;
}