蓝桥杯算法提高VIP-质数的后代 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
int n, m;
const int maxn = 55000;
int a[maxn];
void dabiao()
{
    int t, i;
    for(i = 3; i <= maxn; i += 2){
        a[i] = 1;
    }
    a[2] = 1;
    for(i = 3; i*i <= maxn; i += 2){
        if(a[i] == 1){
           t = 3*i;
           while(t <= maxn){
               a[t] = 0;
               t = t + 2*i;
           }    
        }
    }
}
int fun(int x)
{
    int b;
    for(int i = 2; i <= x/2; i++){
        if(x%i == 0){
            b = x / i;
            if(a[i]==1 && a[b]==1){
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    memset(a, 0, sizeof(a));
    dabiao();
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> m;
        if(fun(m)==0){
            cout <<"Yes"<<endl;
        }
        else{
            cout <<"No"<<endl;
        }
    }
    return 0;
}