质数出击

coding>C++
890 词

题目描述

质数寂寞了很久，这次他们不甘于寂寞，主动出击，寻找自己的后代，无情阻碍它们的合数原来竟然全是质数的后代，因为合数可以由质数相乘结合而得。
已知如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。

输入

第一行一个正整数T，表示需要判断的自然数数量 

接下来T行，每行一个要判断的自然数 

数据规模和约定 
$$ 1< =T< =20 $$
$$ 2< =要判断的自然数< =10^5 $$

输出

共T行，依次对于输入中给出的自然数，判断是否为质数的直接后代，是则输出Yes，否则输出No 

样例输入

1
2
3
4
5
4 
3 
4 
6 
12

样例输出

1
2
3
4
No 
Yes 
Yes 
No

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
bool sushu(int x) {
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)return false;
    return true;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (sushu(n) == true) {
            printf("No\n");
            continue;
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                if (sushu(i) == true && sushu(n / i) == true) {
                    printf("Yes\n");
                    break;
                } else {
                    printf("No\n");
                    break;
                }
            }
        }
    }
    return 0;
}