首页 > 代码库 > HDU2138 随机素数测试 Miller-Rabin算法
HDU2138 随机素数测试 Miller-Rabin算法
题目描述
Give you a lot of positive integers, just to find out how many prime numbers there are..
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.
32-bit signed intege，最普通的肯定要超时，筛选法要超内存，开小的话就越界。
miller_rabin算法
一.费马小定里
if n is prime and gcd(a,n) equals one ,then a^(n-1) = 1 (mod n)
费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael.
前3个Carmichael数是561,1105,1729。
Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。
为此又有二次探测定理,以确保该数为素数:
二.二次探测定理
二次探测定理 如果p是一个素数，0<x<p,则方程x^2≡1(mod p)的解为x=1,p-1
根据以上两个定理,如到Miller-Rabin算法的一般步骤:
0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
1、随机取一个b，2<=b
2、计算v=b^m mod n
3、如果v==1，通过测试，返回
4、令i=1
5、如果v=n-1，通过测试，返回
6、如果i==j，非素数，结束
7、v=v^2 mod n，i=i+1
8、循环到5
说明:
Miller-Rabin是随机算法
得到的结果的正确率为75%,所以应该多次调用该函数,使正确概率提高为1-(1/4)^s
解云鹏你懂了吗？
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <iostream>#include <algorithm>#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;int i, j, k;ll m, b;int numCase;ll n;bool flag;int S = 5;ll quickpow(ll m,ll n,ll k){ int b = 1; while (n > 0){ if (n & 1) b = (b*m)%k; n = n >> 1 ; m = (m*m)%k; } return b;}bool Miller_Rabin(){ int temp_n = n -1; j = 0; while(temp_n % 2 == 0){ ++j; temp_n /= 2; } m = (n -1) / (1 << j); int v = quickpow(b, m, n); if(1 == v){ flag = true; return flag; } int i = 0; while(++i <= 5){ if(v == n - 1){ flag = true; } else if(i == j){ flag = false; return flag; } }}bool witness(ll a,ll n){ ll 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(ll n){ int s[]={2,7,61}; if(n==2) return true; if(n==1 || ((n&1)==0)) return false; for(int i=0;i<3;i++) if(witness(s[i], n)) return false; return true;}int main(){ while(EOF != scanf("%d",&numCase)){ flag = false; int count = 0; while(numCase--){ cin >> n; if(miller_rabin(n)) ++count; } cout << count << endl; } return 0;}