hdu 2138 How many prime numbers(数论:素数判定)

本文主要是介绍hdu 2138 How many prime numbers(数论:素数判定)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为给出的数据是32位,所以可以直接对每个数暴力判定

当然也可以用大素数判定Miller Rabin算法

两份代码如下:

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;bool judge(int n) {int i;int m = (int)sqrt(n+0.5);for(i=2; i<=m; ++i)if(n % i == 0)return false;return true;
}int main(void) {int n, i, cnt, x;while(scanf("%d", &n) != EOF) {cnt = 0;for(i=0; i<n; ++i) {scanf("%d", &x);if(judge(x))cnt++;}cout << cnt << endl;}return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<cmath>
bool witness(__int64 a,__int64 n) {__int64 t, d, x;d = 1;int i=ceil(log(n-1.0)/log(2.0)) - 1;for(; i>=0; i--) {x = d;  d = (d*d)%n;if(d==1 && x!=1 && x!=n-1) return true;if( ((n-1) & (1<<i)) > 0)d = (d*a)%n;}return d==1? false : true;
}
bool miller_rabin(__int64 n) {if(n==2)    return true;if(n==1 || ((n&1)==0))    return false;for(int i=0;i<50;i++){__int64 a=rand()*(n-2)/RAND_MAX +1;if(witness(a, n))    return false;}return true;
}
int main() {int n,cnt;__int64 a;while(scanf("%d",&n)!=EOF) {cnt=0;while(n--) {scanf("%I64d",&a);if(miller_rabin(a))cnt++;}printf("%d\n",cnt);}return 0;
}

这篇关于hdu 2138 How many prime numbers(数论:素数判定)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---