Guest User

Untitled

a guest
Dec 10th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. vector <bool> res;
  9.  
  10. int main()
  11. {
  12. int n=1000001;
  13. vector<char> prime (n+1, true);
  14. prime[0] = prime[1] = false;
  15. for (int i=2; i<=n; ++i)
  16.     if (prime[i])
  17.         if (i * 1ll * i <= n)
  18.             for (int j=i*i; j<=n; j+=i)
  19.                 prime[j] = false;
  20.  
  21. long long t,q;
  22. cin >> t;
  23. for (int i=0;i<t;++i)
  24. {
  25.     cin >> q;
  26.     double s = sqrt ((double)(q));
  27.     if (s==(long long)s)
  28.     {
  29.         if (prime[(long long)s]==true) { res.push_back (true); continue;}
  30.     }
  31.     res.push_back(false);
  32. }
  33.  
  34. for (unsigned i=0;i<res.size();i++)
  35.     if (res[i]) cout <<"YES" << endl;
  36.     else cout << "NO"<<endl;
  37.  
  38. return 0;
  39. }
Add Comment
Please, Sign In to add comment