230B. T-primes

binary search, implementation, math, number theory, 1300, http://codeforces.com/problemset/problem/230/B

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int T;
long long a;
bool np[N + 5]; // np[i] 表示 i 是否为合数（非质数）

// 检查 a 是否为完全平方数且其平方根是奇数质数
bool check() {
    if (a == 4) return 1;  // 特殊情况：4 = 2^2，但 2 是偶数质数，但题目可能允许？这里返回 true

    if (a == 1 || a % 2 == 0) return 0;  // 奇数且不为 1 和偶数

    long long s = sqrt(a);
    if (s * s != a || np[s]) return 0;  // 不是完全平方数 或 平方根不是质数
    return 1;
}

int main() {
    // 使用埃拉托斯特尼筛法预处理出所有小于等于 N 的合数
    for (int i = 3; i * i <= N; i += 2) {
        if (np[i]) continue;
        for (int j = i; j * i <= N; j += 2) {
            np[j * i] = 1;
        }
    }

    // 输入测试次数
    cin >> T;
    while (T--) {
        cin >> a;
        if (check()) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }

    return 0;
}

思路：确实体会到了cpp处理大整数太麻烦了。。。

#include<iostream>
#include<cmath>
#include<unordered_set>
#include<vector>
using namespace std;

int main(){
    int t;
    vector<bool> check(1000001,true);
    unordered_set<int> st;
    cin>>t;
    for(int i=2;i<=1000000;i++){
        if(check[i]) {
            st.insert(i);
            if((long long)i*i<1000000){
                for(long long j=i*i;j<=1000000;j+=i){
                    check[j]=false;
                }
            }
        }
    }
    while(t--){
        long long a;
        cin>>a;
        long long c = sqrt(a);
        if(c*c==a && st.find(c)!=st.end()){cout<<"YES"<<'\n';}
        else {cout<<"NO"<<'\n';}
    }
    return 0;
}