?
本题其实是简单的找规律问题，规律一看就明白了。
这个就是需要总结问题的思维能力。同时需要注意可能的溢出问题。
规律总结错了，溢出问题又错了，结果就不能一次性AC了。
注意：静态内存和全局内存，即栈内存，比动态内存，即堆内存，要大；动态分配一个百万的bool数组也会程序崩溃的。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MAX_N = (int)1E5+1; const int MAX_M = 1000001; bool primes[MAX_M]; void getPrimes() { memset(primes, 0, sizeof(bool)*MAX_M); primes[0] = primes[1] = 1; 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(%I64d, &num); long long t = (long long) sqrt((double)num); if (t * t == num && !primes[t]) puts(YES); else puts(NO); } } return 0; }