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
comments (?)
stdin 
Standard input is empty
stdout 
1
0
1
https://ideone.com/8PEUaf
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!