题解 | #质数因子#

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); //这三个语句用于加速输入输出操作，特别是在处理大量数据时非常有用 [1]
    cin.tie(0);
    cout.tie(0);

    long long n; //如果输入的整数非常大（例如接近 2 × 10^8 + 14），使用 int 类型可能会导致溢出问题。为了确保代码能够正确处理这样的大整数，我们应该使用 long long 类型来存储和处理输入的整数。
    cin>>n;

    while(n%2==0){ //不断将 n 除以 2，并输出 2，直到 n 不能再被 2 整除。[3]
        cout<<"2 ";
        n/=2; 
    }

    for(long long i=3;i*i<=n;i+=2){ //[2]  注意 这里用sqrt(n)和<= 因为有可能i的平方刚好是n  从 3 开始，每隔一个数（即奇数），尝试将 n 除以当前数 i，并将 i 输出，直到 n 不能再被 i 整除。
        while(n%i==0){  //注意 这里用while 不是if 因为有可能这个i可以被除几次
            cout<<i<<" ";
            n/=i;
        }
    }

    if(n>2) cout<<n<<endl; //[3]

    return 0;
}
// 64 位输出请用 printf("%lld")

[1] ios::sync_with_stdio(0);：

• 取消iostream与stdio的同步，这可以提高输入输出的速度，但之后就不能同时使用cin/cout和scanf/printf了。

[2]

[3] if (n > 2) { factors.push_back(n); } 的目的是处理在质因数分解过程中剩余的大于2的质数。如果 n 等于2，这个条件不会成立，因此 n 不会被添加到 factors 列表中。不过，这种情况实际上已经在之前的步骤中处理过了。

让我们详细分析一下代码逻辑，确保即使 n 等于2也能正确处理。

代码逻辑分析

处理因子 2:

   while (n % 2 == 0) {
       factors.push_back(2);
       n /= 2;

• 这个循环会不断将 n 除以 2，并将 2 添加到 factors 列表中，直到 n 不能再被 2 整除。
• 如果 n 最初就是 2，那么这个循环会执行一次，将 2 添加到 factors 列表中，然后 n 变为 1。

处理剩余的质数:

if (n > 2) {
    factors.push_back(n);
}

• 这个条件检查 n 是否大于 2。如果是，则将 n 添加到 factors 列表中。
• 如果 n 最初是 2，经过前面的步骤后，n 会变为 1，因此这个条件不会成立。
• 也就是到这里的时候n不可能为2,只可能是1