fork download
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. #define endl '\n'
  6. #define ll long long
  7. #define pi pair<int, int>
  8. #define f first
  9. #define s second
  10.  
  11. int ipow(ll b, int e, int mod){
  12. int ret = 1;
  13. for(; e; e >>= 1){
  14. if(e & 1) ret = ret * b % mod;
  15. b = b * b % mod;
  16. }
  17. return ret;
  18. }
  19.  
  20. const int ptst = 4;
  21. int p[ptst] = {2, 3, 5, 7};
  22. bool ptest(int x){
  23. if(x < 4) return x > 1;
  24. for(int i = 0; i < ptst; i++) if(x % p[i] == 0) return 0;
  25.  
  26. int y = x - 1, e = __lg(y & -y);
  27. y >>= e;
  28. for(int i = 0; i < ptst; i++){
  29. ll z = ipow(p[i] % x, y, x);
  30. if(z == 1) continue;
  31. for(int i = 0; i < e && z != x - 1; i++) z = z * z % x;
  32. if(z != x - 1) return 0;
  33. }
  34.  
  35. return 1;
  36. }
  37.  
  38. int main(){
  39. ios::sync_with_stdio(0);
  40. cin.tie(0);
  41.  
  42. cout << ptest(1000000007) << endl;
  43. cout << ptest(1350451049) << endl;
  44. cout << ptest(1000696969) << endl;
  45.  
  46. return 0;
  47. }
Success #stdin #stdout 0s 4332KB
stdin
Standard input is empty
stdout
1
0
1