提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

HDU 2138 How many prime numbers

HDU How many Numbers Prime
2023-09-11 14:15:28 时间

How many prime numbers

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2138
64-bit integer IO format: %I64d      Java class name: Main
 Give you a lot of positive integers, just to find out how many prime numbers there are.
 

Input

  There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.
 

Output

  For each case, print the number of prime numbers you have found out.
 

Sample Input

3
2 3 4

Sample Output

2

Source

HDU 2007-11 Programming Contest_WarmUp
 
解题：miller - rabbin 素性测试
其实我们判的是伪素数，伪素数就是这个数很有可能是素数，但是不排除不是素数的可能，一旦miller rabin判断某个数不是素数，那么这个数一定不是素数，如果判断这个数是素数，则这个数是伪素数。由费马定理
$a^{p-1} \equiv 1(mod \quad p)$
 那么我们可以把p-1表示成
$p - 1 = d*2^{r}$
那么很明显
　$a^{p-1} = a^{d*2^{r}}$
如果
$a^{d} \equiv 1 (mod \quad p)$ 
那么
$a^{d}$ $a^{2d} \dots$ $a^{d*2^{r}}$
都能模p余1
所以p是伪素数，如果
$a^{d}  \not\equiv 1(mod\quad p)$
那么我们只需要看看
$a^{d*2^{i}} mod\quad p == p-1\qquad i < r$
么，存在，那么
$a^{p-1} \equiv 1(mod\quad p)$
成立，否则，这个数一定是合数
 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL quickPow(LL a,LL d,LL n){
 5     LL ret = 1;
 6     while(d){
 7         if(d&1) ret = (ret*a)%n;
 8         d >>= 1;
 9         a = (a*a)%n;
10     }
11     return ret;
12 }
13 bool check(int a,int d,int n){
14     if(n == a) return true;
15     while(~d&1) d >>= 1;
16     LL t = quickPow(a,d,n);
17     while(d < n-1 && t != 1 && t != n-1){
18         t = t*t%n;
19         d <<= 1;
20     }
21     return (d&1) || t == n-1;
22 }
23 bool isP(int n){
24     if(n == 2) return true;
25     if(n < 2 || 0 == (n&1)) return false;
26     static int p[3] = {2,3,61};
27     for(int i = 0; i < 3; ++i)
28         if(!check(p[i],n-1,n)) return false;
29     return true;
30 }
31 int main(){
32     int n,cnt,tmp;
33     while(~scanf("%d",&n)){
34         cnt = 0;
35         while(n--){
36             scanf("%d",&tmp);
37             cnt += isP(tmp);
38         }
39         printf("%d\n",cnt);
40     }
41     return 0;
42 }
View Code

 

相关文章