FOJ 1075 分解素因子
程序员文章站
2022-03-04 23:01:22
...
一,问题描述
注意:输入一个测试用例后,第二行会立即输出这个测试用例的结果,并不是等所有测试用例都输入后,再一次性输出所有测试用例
正确输入输出格式:
2
11
11
9828
2*2*3*3*3*7*13
二,问题分析
问题的求解思路如下:首先把所有1到65535范围内的所有素数找出来,并用数组保存,对于每一个测试用例,依次用素数数组的元素从小到大比较,如果能够被整除,就输出该元素,注意输出的格式要求。
三,问题解答
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector<int> sushu; //1到65535之间的所有素数
int judge(int n) {
int k = (int)sqrt((double)n); //sqrt的参数类型为double
for (int i = 2; i <= k; i++) {
if (n % i == 0) {
return 0; //不是素数
}
}
return 1; //n是素数
}
void fun(vector<int>& vec) { //存储素数数组
for (int i = 2; i <= 65535; i++) {
if (judge(i) == 1) {
vec.push_back(i);
}
else {
continue;
}
}
}
int main() {
int num; //测试样例个数
fun(sushu);
while (cin >> num) {
for (int i = 0; i < num; i++) {
int n;
cin >> n;
int k = 0;
int flag = 0; //用于控制输出格式
while (sushu[k] <= n) {
if (n % sushu[k]==0) {
if (flag==0) { //第一个只输出数字
cout << sushu[k];
}
else {
cout << "*" << sushu[k];
}
flag++;
n = n / sushu[k];
}
else {
k++;
}
}
cout << endl;
}
}
return 0;
}