文章來源：http://www.zghlxwxcb.cn/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;
}
?文章來源地址http://www.zghlxwxcb.cn/news/detail-623508.html
到了這里，關(guān)于HDU-2138-大素?cái)?shù)的判斷板子-c語(yǔ)言最快判斷素?cái)?shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
