int power(int x, unsigned int y, int p) {
int res = 1;
x %= p;
while (y > 0) {
if (y % 2) res = (res * x) % p;
y /= 2;
x = (x * x) % p;
}
return res;
}
bool miillerTest(int d, int n) {
int a = 2 + rand() % (n - 4); // Pick a random number in [2..n-2], n > 4
int x = power(a, d, n);
if (x == 1 || x == n - 1) return true;
while (d != n - 1) {
x = (x * x) % n;
d *= 2;
if (x == 1) return false;
if (x == n - 1) return true;
}
return false; // composite
}
bool isPrime(int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
int d = n - 1;
while (d % 2 == 0) d /= 2;
for (int i = 0; i < k; i++)
if (!miillerTest(d, n)) return false;
return true;
}