素数判断
链接：https://ac.nowcoder.com/acm/contest/93963/B链接：https://ac.nowcoder.com/acm/contest/93963/B
来源：牛客网
题目描述
给出一个数x，判断它是否为素数，并输出所有它的素因子。
输入描述:
第1行输入组数T，代表有T组数据。
第2-T+1行每行输入一个数x表示对应询问。
数据保证：2≤x≤109
输出描述:
对于每组询问输出两行表示结果。
第1行，如果x是素数，输出“isprime”（不含双引号），否则输出“noprime”（不含双引号）。
第2行，输出x的素因子。
示例1
输入
复制
3
2
9
10
输出
复制
isprime
2
noprime
3
noprime
2 5
#include<iostream>
#include<set>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
void findPrimeFactors(int n) {
set<int> factors;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.insert(i);
n /= i;
}
}
if (n > 1) factors.insert(n);
for (int factor : factors) {
cout << factor << " ";
}
cout << endl;
}
int main(){
int g;
cin >> g;
while (g--) {
int n;
cin >> n;
if (isPrime(n)) {
cout << "isprime" << endl << n << endl;
} else {
cout << "noprime" << endl;
findPrimeFactors(n);
}
}
return 0;
}
这道题通过询问同学了解到了set函数
可以使用set避免输出相同的数据
