fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define endl "\n"
  6.  
  7. int power(int a, int d, int n){
  8. 	int res = 1;
  9. 	a %= n;
  10. 	while(d > 0){
  11. 		if(d % 2 == 1)res = (res * a) % n;
  12. 		a = (a * a)% n;
  13. 		d /= 2;
  14. 	}
  15. 	return res;
  16. }
  17.  
  18. bool millerRabin(int n, int a){
  19. 	if(n % a == 0 && n != a)return false;
  20. 	int d = n - 1;
  21. 	while(d % 2 == 0)d /= 2;
  22. 	int x = power(a,d,n);
  23. 	if(x == 1 || x == n - 1)return true;
  24. 	while(d != n - 1){
  25. 		x = (x * x) % n;
  26. 		d *= 2;
  27. 		if(x == 1)return false;
  28. 		if(x == n - 1)return true;
  29. 	}
  30. 	return false;
  31. }
  32.  
  33. bool isprime(int n){
  34. 	if(n < 2)return false;
  35. 	if(n < 4)return true;
  36. 	if(n % 2 == 0)return false;
  37. 	int test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  38.     for (int i = 0; i < 12; i++) {
  39.         if (test[i] >= n) break;
  40.         if (!millerRabin(n, test[i])) return false;
  41.     }
  42.     return true;
  43. }
  44.  
  45. signed main(){
  46. 	ios_base::sync_with_stdio(0);
  47.     cin.tie(0);cout.tie(0);
  48.     int t; cin >> t;//max = 500 
  49.     while(t--){
  50.     	int n; cin >> n;
  51.     	if(isprime(n)){
  52.     		cout << "YES" << endl;
  53. 		}
  54. 		else cout << "NO" << endl;
  55. 	}
  56. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
9223372036854775807
stdout
copy 
NO
https://ideone.com/2MN9PO
language:
C++ (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!