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    }