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

本文主要是介绍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;
}

这篇关于hdu 2138 How many prime numbers （随即素数测试模版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---