题解：SP10818 FACTCG2 - Medium Factorization

题意

这道题要求将一个整数分解为质因数的乘积，并在表达式中包含数字

1

。解题的关键在于正确找出所有质因数，并按照要求的格式输出。

思路

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

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

代码

CPP

#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;
}

题解：SP10818 FACTCG2 - Medium Factorization

文章操作

题意

思路

代码

相关推荐

评论

题解：SP10818 FACTCG2 - Medium Factorization