跳至正文

1 条题解

  • 0
    @ 2026-10-8 18:53:36

    【本题解由站长编写】

    试除法分解质因数:从 2 开始试到 √n,每找到一个因数就整除一次并记录。⚠️ 输出要去重:题目要的是「所有质因子」,重复的同一质因子只输出一次(实测 n=12 输出 2 3,不是 2 2 3),所以每除尽后直接跳到下一个 d。剩下的 x > 1 是一个大于 √n 的质因子,补在末尾。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        vector<int> fac;
        int x = n;
        for (int d = 2; (long long)d * d <= x; d++) {
            if (x % d == 0) {
                fac.push_back(d);
                while (x % d == 0) x /= d;   // 除尽,保证质因子不重复输出
            }
        }
        if (x > 1) fac.push_back(x);
        for (size_t i = 0; i < fac.size(); i++) {
            if (i) cout << " ";
            cout << fac[i];
        }
        cout << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4217
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者