题目：HDU 2138

题目大意：

多组输入 每组输入一组数字 输出有多少个数是质数

输入

3
2 3 4

输出

2

应用到两个定理费马小定理和二次探测定理

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n, ans;

ll mod_mul(ll a, ll b, ll mod){
    ll res = 0;
    while(b){
        if(b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

ll mod_pow(ll a, ll b, ll mod){
    ll res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

bool Miller_Rabin(ll n){
    if(n == 2) return true;
    if(n < 2 || !(n & 1)) return false;
    ll m = n - 1, k = 0;
    while(!(m & 1)){
        k ++;
        m >>= 1;
    }
    for(int i = 1; i <= 20; ++ i){
        ll a = rand() % (n - 1) + 1;
        ll x = mod_pow(a, m, n);
        ll y;
        for(int j = 1; j <= k; ++ j){
            y = mod_mul(x, x, n);
            if(y == 1 && x != 1 && x != n - 1) return false;
            x = y;
        }
        if(y != 1) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n){
        ans = 0;
        for(int i = 0; i < n; ++ i){
            ll x;
            cin >> x;
            if(Miller_Rabin(x)) ans ++;
        }
        cout << ans << endl;
    }
    return 0;
}