文章来源：https://www.toymoban.com/news/detail-623508.html
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll fast_pow(ll x, ll y, ll m)
{
ll res = 1;
x %= m;
while (y)
{
if (y & 1)res = (res * x) % m;
x = (x * x) % m;
y >>= 1;
}
return res;
}
bool witness(ll a, ll n)
{
ll u = n - 1;
int t = 0;
while (u & 1 == 0)u = u >> 1, t++;
ll x1, x2;
x1 = fast_pow(a, u, n);
for (int i = 1; i <= t; i++)
{
x2 = fast_pow(x1, 2, n);
if (x2 == 1 && x1 != 1 && x1 != n - 1)return true;
x1 = x2;
}
if (x1 != 1)return true;
return false;
}
int miller_rabin(ll n, int s)
{
if (n < 2)return 0;
if (n == 2)return 1;
if (n % 2 == 0)return 0;
for (int i = 0; i < s && i < n; i++)
{
ll a = rand() % (n - 1) + 1;
if (witness(a, n))return 0;
}
return 1;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
while (cin >> n)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
ll a;
cin >> a;
int s = 50;
cnt += miller_rabin(a, s);
//cout << cnt <<"*"<< endl;
}
cout << cnt << endl;
}
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-623508.html
到了这里，关于HDU-2138-大素数的判断板子-c语言最快判断素数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
