codeforces T-primes 230 B 素数题解 - c++编程基础

本题其实是简单的找规律问题，规律一看就明白了。

这个就是需要总结问题的思维能力。同时需要注意可能的溢出问题。

规律总结错了，溢出问题又错了，结果就不能一次性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; }