fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define all(x) (x).begin(), (x).end()
  5. #define rall(x) (x).rbegin(), (x).rend()
  6.  
  7. using namespace std;
  8. int main()
  9. {
  10. ios_base::sync_with_stdio(false), cin.tie(0);
  11.  
  12. int n, c = 0, gcd = 0;
  13. cin >> n;
  14. vector <int> a(n);
  15. vector <vector<int>> p(1e6+10);
  16. set <int> comp;
  17.  
  18. for (int i = 0; i < n; i++)
  19. cin >> a[i], gcd = __gcd(gcd, a[i]);
  20. vector<int> spf(1e6+10);
  21. for(int i=2;i*i<=1e6+10;i++){
  22. if(spf[i]) continue;
  23. for(int j=i*i;j<=1e6+10;j+=i){
  24. spf[j] = i;
  25. }
  26. }
  27. for(int i=2;i<=1e6;i++){
  28. if(!spf[i])spf[i] = i;
  29. }
  30. for(int i=0;i<n;i++){
  31. if(p[a[i]].size()) continue;
  32. int x = a[i];
  33. while(x>1){
  34. if(p[a[i]].size()==0 || spf[x]!=p[a[i]].back()) p[a[i]].push_back(spf[x]);
  35. x /= spf[x];
  36. }
  37. }
  38.  
  39. for (int i = 0; i < n; i++)
  40. {
  41. c += p[a[i]].size();
  42. for (auto j : p[a[i]])
  43. comp.insert(j);
  44. }
  45. if (comp.size() < c && gcd == 1)
  46. cout << "setwise coprime";
  47.  
  48. else if (comp.size() == c)
  49. cout << "pairwise coprime";
  50.  
  51. else
  52. cout << "not coprime";
  53. return 0;
  54. }
  55.  
Success #stdin #stdout 0.02s 30480KB
stdin
Standard input is empty
stdout
pairwise coprime