题解：SP10818 FACTCG2 - Medium Factorization

zhangmuning1016 · 2025-05-16 15:50:58 · 题解

题意

这道题要求将一个整数分解为质因数的乘积，并在表达式中包含数字 1。解题的关键在于正确找出所有质因数，并按照要求的格式输出。

思路

采用试除法进行质因数分解。

• 将 2 单独处理。
• 从 3 开始处理，检查奇数作为可能的质因数。
• 循环结束后，如果 N>1，说明 N 本身是一个质数，添加到结果中。

• 结果中包含数字 1。

  代码

  #include <bits/stdc++.h>
  using namespace std;
  int main() {
  int n;
  while(cin >> n) {
      vector<int> v;
      v.push_back(1);
      if (n > 1) {
          while (n % 2 == 0) {
              v.push_back(2);
              n /= 2;
          }
          for (int i = 3; i * i <= n; i += 2) {
              while (n % i == 0) {
                  v.push_back(i);//此数符合要求 
                  n /= i;
              }
          }
          if (n > 1) {
              v.push_back(n);//说明 n 现在为质数，加入数组 
          }
      }
  
      cout << v[0]; //结果包含 1 
      for (int i = 1; i < v.size(); i++) {
          cout << " x " << v[i];//输出答案 
      }
      cout << endl;
  }
  return 0;
  }