How many prime numbers
Problem Description
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
Author
wangye
Source
HDU 2007-11 Programming Contest_WarmUp
题目类型：Miller_Rabin素数测试
算法分析：直接使用筛法打表会TLE，这里使用Miller_Rabin来加速素数测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 10000 + 66; const int testnum = 8; //随机算法判定次数，一般8~10就够了 // 计算ret = (a*b)%c a,b,c < 2^63 long long mult_mod (long long a,long long b,long long mod) { a %= mod; b %= mod; long long ans = 0; long long temp = a; while (b) { if (b & 1) { ans += temp; if (ans > mod) ans -= mod;//直接取模慢很多 } temp <<= 1; if (temp > mod) temp -= mod; b >>= 1; } return ans; } long long pow_mod (long long a,long long n,long long mod) { long long ans = 1; long long temp = a % mod; while (n) { if (n & 1) ans = mult_mod (ans, temp, mod); temp = mult_mod (temp, temp, mod); n >>= 1; } return ans; } // 通过 a^(n-1)=1(mod n)来判断n是不是素数 // n-1 = x*2^t 中间使用二次判断 // 是合数返回true, 不一定是合数返回false bool check (long long a, long long n, long long x, long long t) { long long ans = pow_mod (a, x, n); long long last = ans; for(int i = 1; i <= t; i++) { ans = mult_mod (ans, ans, n); if(ans == 1 && last != 1 && last != n - 1) return true;//合数 last = ans; } if(ans != 1) return true; else return false; } //************************************************** // Miller_Rabin算法 // 是素数返回true,(可能是伪素数) // 不是素数返回false //************************************************** bool Miller_Rabin (long long n) { if (n < 2) return false; if (n == 2) return true; if ((n&1) == 0) return false;//偶数 long long x = n - 1; long long t = 0; while ((x&1) == 0) { x >>= 1; t++; } srand (time (NULL)); for (int i = 0; i < testnum; i++) { long long a = rand () % (n - 1) + 1; if (check (a, n, x, t)) return false; } return true; } int main() { // ifstream cin ("aaa.txt"); long long n; while (cin >> n) { long long sum = 0, temp; for (int i = 0; i < n; i++) { cin >> temp; if (Miller_Rabin (temp)) sum++; } cout << sum << endl; } return 0; } |
- « 上一篇：hdu2098
- hdu2141：下一篇 »