费马素性检验c++代码
时间: 2023-12-06 11:36:03 浏览: 32
以下是C++实现的费马素性检验代码:
```c++
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
// 快速幂取模
long long quickPow(long long a, long long b, long long p) {
long long res = 1 % p;
while (b > 0) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
// 费马素性检验
bool fermatTest(long long n, int k) {
if (n == 2) {
return true;
}
if (n < 2 || n % 2 == 0) {
return false;
}
srand(time(NULL));
for (int i = 0; i < k; i++) {
long long a = rand() % (n - 2) + 2;
if (quickPow(a, n - 1, n) != 1) {
return false;
}
}
return true;
}
int main() {
long long n;
int k;
cout << "Please input a number and the number of tests:" << endl;
cin >> n >> k;
if (fermatTest(n, k)) {
cout << n << " is probably a prime number." << endl;
} else {
cout << n << " is definitely not a prime number." << endl;
}
return 0;
}
```