fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define BUFF ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  3. #define FOR(a,b,i) for(int i=(a);i<=(b);i++)
  4. #define REV(a,b,i) for(int i=(a);i>=(b);i--)
  5. #define LOW(v,x) lower_bound(v.begin(),v.end(),x)
  6. #define UP(v,x) upper_bound(v.begin(),v.end(),x)
  7. #define SZ(x) ((int)x.size())
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define INP(a) freopen(a,"r",stdin);
  12. #define OUT(a) freopen(a,"w",stdout);
  13.  
  14. template<typename T>bool maximize(T& x,const T& y){return (x<y)?x=y,1:0;}
  15. template<typename T>bool minimize(T& x,const T& y){return (x>y)?x=y,1:0;}
  16.  
  17. using namespace std;
  18. using ll=long long;
  19. using pa=pair<int,int>;
  20. using str=string;
  21.  
  22. const int INF=1e9;
  23. const int N=1e5+1;
  24. const int A=1e3+1;
  25.  
  26. ll randInt(ll l,ll r){
  27. 	return l+rand()%(r-l+1);
  28. }
  29.  
  30. ll multiply(ll a,ll k,ll n){
  31. 	ll res=0;
  32. 	while(k){
  33. 		if(k&1)res=(res+a)%n;
  34. 		a=(a+a)%n;
  35. 		k/=2;
  36. 	}
  37. 	return res;
  38. }
  39.  
  40. ll binaryPower(ll a,ll k,ll n){
  41. 	ll res=1;
  42. 	while(k){
  43. 		if(k&1)res=multiply(res,a,n);
  44. 		a=multiply(a,a,n);
  45. 		k/=2;
  46. 	}
  47. 	return res;
  48. }
  49.  
  50. bool test(ll a,ll n,int k,ll m){ //2^k * m
  51. 	ll mod=binaryPower(a,m,n);
  52. 	if(mod==1||mod==n-1)return 1;
  53.  
  54. 	FOR(1,k-1,i){
  55. 		mod=multiply(mod,mod,n);
  56. 		if(mod==n-1)return 1;
  57. 	}
  58. 	return 0;
  59. }
  60.  
  61. bool RabinMiller(ll n){
  62. 	static vector<int>checkSet={2,3,5,7,11,13,17,19,23,29,31,37};
  63. 	for(int x:checkSet){
  64. 		if(n==x)return 1;
  65. 	}
  66. 	if(n<41)return 0;
  67.  
  68. 	int k=0;
  69. 	ll m=n-1;
  70. 	while(m%2==0){
  71. 		m/=2;
  72. 		k++;
  73. 	}
  74. 	for(int a:checkSet){
  75. 		if(!test(a,n,k,m))return 0;
  76. 	}
  77. 	return 1;
  78. }
  79.  
  80. void solve(){
  81. 	int t;
  82. 	cin>>t;
  83. 	while(t--){
  84. 		ll n;
  85. 		cin>>n;
  86. 		cout<<(RabinMiller(n)?"YES\n":"NO\n");
  87. 	}
  88. }
  89.  
  90. int main(){
  91. 	srand(time(nullptr));
  92. 	// INP("rabinmiller.inp")
  93.     BUFF
  94.     solve();
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
10
1000000007
1000005277
1000002277
41041
561
2
90
10
113
41
stdout
copy 
YES
YES
YES
NO
NO
YES
NO
NO
YES
YES
https://ideone.com/7sGRwM
problem PON, based on SPOJ submission 34978598 (CPP14), 2025-08-30 18:34:46
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!