jakaria_hossain

Codeforce - T-Primes

May 14th, 2019
87
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fastread()(ios_base::sync_with_stdio(false),cin.tie(NULL));
  5.  
  6. #define SZ 100000004
  7. bool prime[SZ];
  8. void primeset()
  9. {
  10. ll i,j;
  11. prime[0] = prime[1] = true;
  12.  
  13. for (i=4; i<SZ; i+=2)
  14. prime[i] = true;
  15.  
  16. for (i=3; i*i<=SZ; i+=2)
  17. if (!prime[i])
  18. for (j=i*i; j<SZ; j+=2*i)
  19. prime[j] = true;
  20. }
  21. int main()
  22. {
  23. fastread();
  24. primeset();
  25. ll t;
  26. scanf("%I64d",&t);
  27. while(t--)
  28. {
  29. ll n;
  30. scanf("%I64d",&n);
  31. ll r=sqrt(n);
  32. if(!prime[r] && r*r==n)
  33. printf("YES\n");
  34. else
  35. printf("NO\n");
  36. }
  37. return 0;
  38. }
RAW Paste Data