FreakSkipper

E. Problem-T

Oct 29th, 2020 (edited)
931
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define vi vector<int>
  6. #define ll long long
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define mp make_pair
  10. #define ii pair<int, int>
  11.  
  12. #define MAX 1000000000000
  13.  
  14. vector<ll> crivo(ll n) {
  15.     vector<bool> ehprimo(n+1, true);
  16.     vector<ll> primos;
  17.  
  18.     ehprimo[1] = false;
  19.     primos.eb(2);
  20.     primos.eb(3);
  21.     for (ll i = 3; i <= n; i+=2) {
  22.         ehprimo[i+1] = false;
  23.         if (ehprimo[i]) {
  24.             primos.eb(i);
  25.  
  26.             for (int x = i+i; x <= n; x+=i) {
  27.                 ehprimo[x] = false;
  28.             }
  29.         }
  30.     }
  31.  
  32.     return primos;
  33. }
  34.  
  35. int main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(NULL);
  38.  
  39.     int q;
  40.     scanf("%d", &q);
  41.  
  42.     vector<ll> primos = crivo(1000000);
  43.     for (int i = 0; i < q; i++) {
  44.         ll x;
  45.         scanf("%lld", &x);
  46.  
  47.         bool res = false;
  48.         ll l = 0, r = primos.size()-1;
  49.         while(l <= r) {
  50.             ll mid = (l+r)/2;
  51.             if (primos[mid]*primos[mid] == x) {
  52.                 res = true;
  53.                 break;
  54.             } else if (primos[mid]*primos[mid] < x) {
  55.                 l = mid + 1;
  56.             } else {
  57.                 r = mid - 1;
  58.             }
  59.         }
  60.  
  61.         if (res) {
  62.             printf("1\n");
  63.         } else {
  64.             printf("0\n");
  65.         }
  66.     }
  67.  
  68.     return 0;
  69. }
RAW Paste Data