蓝桥杯 ADV-154 算法提高质数的后代

问题描述
在上一季里，曾提到过质数的孤独，其实从另一个角度看，无情隔膜它们的合数全是质数的后代，因为合数可以由质数相乘结合而得。
如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。
输入格式
第一行一个正整数T，表示需要判断的自然数数量
接下来T行，每行一个要判断的自然数
输出格式
共T行，依次对于输入中给出的自然数，判断是否为质数的直接后代，是则输出Yes，否则输出No
样例输入
4
3
4
6
12
样例输出
No
Yes
Yes
No
数据规模和约定
1<=T<=20
2<=要判断的自然数<=105

#include <iostream>
#include <vector>
using namespace std;
int a[100005] = {0};
vector<int> p;
void getprime() {
    a[0] = a[1] = 1;
    for (int i = 2; i * i <= 100000; i++) {
        if (a[i] == 0) {
            for (int j = i * i; j <= 100000; j = j + i) 
                a[j] = 1;
        }
    }
    for (int i = 2; i <= 100000; i++) 
        if (a[i] == 0) p.push_back(i);
}
void check(int n) {
    for (int i = 0; i < p.size(); i++) {
        if (n % p[i] == 0 && a[n / p[i]] == 0) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}
int main() {
    getprime();
    int n, k;
    cin >> k;
    while (k--) {
        cin >> n;
        check(n);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int a[100005] = {0};

vector<int> p;

void getprime() {

a[0] = a[1] = 1;

for (int i = 2; i * i <= 100000; i++) {

if (a[i] == 0) {

for (int j = i * i; j <= 100000; j = j + i)

a[j] = 1;

}

for (int i = 2; i <= 100000; i++)

if (a[i] == 0) p.push_back(i);

}

void check(int n) {

for (int i = 0; i < p.size(); i++) {

if (n % p[i] == 0 && a[n / p[i]] == 0) {

cout << "Yes\n";

return;

}

cout << "No\n";

}

int main() {

getprime();

int n, k;

cin >> k;

while (k--) {

cin >> n;

check(n);

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版