B3871 [GESP202309 五级] 因数分解 题解

· · 题解

Solution

题目传送门

题目分析

这道题要求对一个正整数进行质因数分解，并按照格式输出。质因数分解是将一个正整数分解为若干素数（质数）相乘的形式。如 6 可以分解为 2 \times 3，20 可以分解为 2^2 \times 5。

解题步骤

  1. 从最小的质数 2 开始，逐个检查每个数是否是给定数字的因数。
  2. 当发现一个因数时，通过循环除以这个因数，计算它出现的次数 cnt。
  3. 对于大于 \sqrt{n} 的部分，如果 n 大于 1，则 n 本身就是一个因数。
  4. 格式化输出：根据题目要求格式化输出结果。当一个因数出现多次时，使用指数形式表示。

AC Code

#include<iostream>
#define ll long long
using namespace std;
int main(){
    ll n; cin >> n;
    bool flag = true; //flag 用于控制输出格式
    for (ll i = 2; i * i <= n; i++){
        int cnt = 0; //cnt 表示因数 i 出现的次数
        while (n % i == 0){ //当 i 是 n 的因子时
            n /= i; //除以因子 i
            cnt++; //增加 cnt
        }
        if (cnt > 0){ //如果 i 是因子
            if (!flag) cout << " * "; //如果不是第一个因子，输出乘号
            cout << i; //输出因子
            if (cnt > 1) cout << "^" << cnt; //如果因子出现多次，输出指数形式
            flag = false; //更新 flag
        }
    }
    if (n > 1){ //如果剩余的 n 大于 1，代表 n 本身就是一个因数
        if (!flag) cout << " * ";
        cout << n;
    }
    return 0;
}

时间复杂度：O(\sqrt{n})，可以通过本题。