素数判断

链接：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避免输出相同的数据