Codeforces 230B T-primes：質數平方判斷與篩法優化

題目大意

給定 n 個數 x_i (≤ 10¹²)，判斷每個數是否為 T-prime：即存在質數 p 使得 x = p²。

核心規律

x 是 T-prime ⇔ x 是完全平方數 且 其平方根是質數。因為只有質數的平方恰好有三個約數：1, p, p²。

算法步驟

1. 預處理：埃氏篩求出 10⁶ 以內所有質數（因 √10¹² = 10⁶）。
2. 對每個查詢 x：計算 t = (long long)sqrt(x)，檢查 t*t == x 且 t 是質數。
3. 注意：sqrt 精度問題，用 (long long)sqrt((double)x) 並驗證平方。

完整 C++ 代碼

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX_M = 1000001;
bool primes[MAX_M];

void getPrimes() {
    memset(primes, 0, sizeof(primes));
    primes[0] = primes[1] = true;
    for (int i = 2; i < MAX_M; i++) {
        if (!primes[i]) {
            for (int j = i<<1; j < MAX_M; j += i)
                primes[j] = true;
        }
    }
}

int main() {
    getPrimes();
    int n; long long num;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lld", &num);
            long long t = (long long)sqrt((double)num);
            if (t * t == num && !primes[t]) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

關鍵避坑指南

• 靜態/全局數組：bool primes[1000001] 放全局或靜態，避免棧溢出。
• 長長整型：num 和 t*t 必須用 long long（64 位）。
• 平方根精度：sqrt 返回 double，轉長整型後必須驗證 t*t == num。
• 輸入輸出：大量數據用 scanf/printf，避免 cin/cout 慢（或加 ios::sync_with_stdio(false)）。