hdu 2138 How many prime numbers
ACM STEPS里的...这题前面一道是求LCM....结果接下来就是这么一道。。。 朴素会超....筛法会爆....题目顺序真是按照难度来的？ 于是想到 Miller-Rabin素数测试....... 这个方法是基于费马小定理 我的理解就是... 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的...暂时还是算了吧...论文里貌似扯了一大堆 第一次用，竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表，然后每次random选取若干个进行判断...那样应该更可靠些？ 本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水？
1
2 /* ***********************************************
3 Author :111qqz
4 Created Time :2016年02月19日 星期五 16时54分19秒
5 File Name :code/hdu/2138.cpp
6 ************************************************ */
7
8 #include <iostream>
9 #include <cmath>
10 #include <stdio.h>
11 #include <cstring>
12
13 using namespace std;
14
15 typedef long long LL;
16 LL power(LL m,LL n,LL k)
17 {
18 int b = 1;
19 while (n > 0)
20 {
21 if (n & 1)
22 b = (b*m)%k;
23 n = n >> 1 ;
24 m = (m*m)%k;
25 }
26 return b;
27 }
28 bool judge(LL n)
29 {
30 LL i;
31 if (n<=3) return true;
32 for (i=2;i<=ceil(sqrt(n))+1;i++)
33 if (n %i==0) return false;
34 return true;
35 }
36
37 int main()
38 {
39 LL i,n,x;
40
41 while (scanf("%I64d",&n)!=EOF)
42 { LL ans=0;
43 for (i=1;i<=n;i++)
44 {
45 scanf("%I64d",&x);
46 if ((power(61,x-1,x)==1)&&(power(11,x-1,x)==1)&&(power(31,x-1,x)==1)
47 &&(power(97,x-1,x)==1))
48 ans++;
49 }
50 printf("%I64d\n",ans);
51 }
52 return 0;
53 }