hdu 2138 How many prime numbers （随即素数测试模版）

//题意：输入N个数，输出素数的个数。 

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

long long bigpow(long long x,long long n, long long M){

    long long res=1,temp=x%M;

    while(n){

        if(n&1){

            res=(res*temp)%M;

        }

        temp=(temp*temp)%M;

        n>>=1;

    }

    return res;

}

long long miller(long long n, long long s=50){

    if(n==2)return 1;

    if(n%2==0)return 0;

    long long j, a;

    for(j=0; j<s; j++){

        a=rand()*(n-2)/RAND_MAX+1;

        if(bigpow(a, n-1, n)!=1)return 0;

    }

    return 1;

}

int main(){

    int T, ans;

    long long n;

    while(scanf("%d", &T)!=EOF){

        ans=0;

        while(T--){

            scanf("%I64d", &n);

            if(miller(n))

            ans++;

        }

        printf("%d\n", ans);

    }

    return 0;

}