1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
| #include <iostream> #include <cmath>
using namespace std;
long long mulRem(long long a, long long b, long long p) { if (b == 0) return 0; if (b == 1) return a % p;
if ((b & 1) == 0) return mulRem((a << 1) % p, b >> 1, p); else return (mulRem((a << 1) % p, b >> 1, p) + a) % p; }
long long powRem(long long a, long long power, long long p) { if (power == 0) return 1; if (power == 1) return a % p; if ((power & 1) == 0) return powRem(mulRem(a, a, p), power >> 1, p); else return mulRem(powRem(mulRem(a, a, p), power >> 1, p), a, p); }
bool minerRabin(long long n, int S) { const int A[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
if (n <= 2) { if (n == 2) return true; else return false; }
if ((n & 1) == 0) return false;
long long u = n - 1; while ((u & 1) == 0) u = u >> 1;
for (int i = 0; i < S; i++) { long long v = u; int a = A[i]; if (a >= n) break; long long x = powRem(a, v, n); v = v << 1; while (v < n) { long long y = mulRem(x, x, n); if (y == 1 && x != 1 && x != n - 1) return false; x = y; v = v << 1; } if (x != 1) return false; }
return true; }
int main() { int t = 0; cin >> t; long long *a = new long long[t]; for (int i = 0; i < t; i++) cin >> a[i]; for (int i = 0; i < t; i++) cout << (minerRabin(a[i], 12) ? "Yes" : "No") << endl; delete[] a; return 0; }
|