[算法]求质数的算法之Miller-Rabin算法，C语言实现
今天讲点比较高级的算法，目的也很简单，求质数，但是应用一种新的算法Miller-Rabin算法，这是一种利用了概率和费马小定理的算法设计，有点玄乎吧，其实本人也是刚接触这种算法，这是一种纯数学的解法，如果各位不懂，当学习一下数学也好啊好，我们往下讲
首先了解基本的数学知识，费马小定理：
若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)mod n=1;
作者Fermat 很牛的数学家，在他在世的时候好像还没有计算机，不过今天我们要用这个定理来设计算法
分析这个定理可以知道，如果一个数是质数，那么它必定满足任意一个整数属于(1，n-1)范围有a^(n-1)mod n=1，不懂？我们取逆否命题试试看，就是只要存在在(1，n-1)范围中的整数a 使得a^(n-1)mod n=1不成立，那么这个数就不是素数，相信明白了吧，我们要确定一个数是否是素数，只要随机生成一系列的数a，如果这些数a使N满足费马小定理的话那么就可以认定它是素数了，当然有个前提，就是这个推导只能在计算机领域内使用就跟我上次讲的用哥德巴赫猜想优化一道算法题目一样，在计算机可以运算的数的范围内可用，请不要在其他科学领域类使用
算法如下，原本是网络上的一个C++算法，我改成C
/* *费马小定理的应用，求质数 *Miller-Rabin算法 *2008 12 27 */ #include"stdio.h" #include"stdlib.h" #include"math.h" #include"time.h" int Btest(int a,int n) { int s = 0; int t = n-1; int i , j , k; int x = 1; int y; i = 1; do{ s++; t = t / 2; }while((t%2)!=1); while(i < = t){ x = ( x * a ) % n; i++; } if((x == 1) || ( x == n-1)) return 1; for(j = 1 ; j <= s - 1 ; j++){ y = 1; for(k = 1 ; k <= j ; k++) { y = 2 * y; } i = 1; x = 1; while(i <= ( y * t)){ x = ( x * a) % n; i++; } if(x == n - 1) return 1; } return 0; } int MillRab(int n) { int a; /*利用时间作为随机种子产生随机数*/ a=random((unsigned)time(0))%(n-3)+2; return Btest(a,n); } int MillerRabin(int n,int k) { int i; for(i=1;i<=k;i++) { if(MillRab(n)==0)return 0; } return 1; } int main(){/*费马小定理的应用*/ int i; int n=10000;/*定义测试范围*/ int count=0; printf("2 3 ");/*先输出2跟3*/ for(i=5;i<=n;){/*从5开始循环判断*/ if(MillerRabin(i , (int)log10(i))){/*符合条件？*/ printf("%d ",i); count++; } i=i+2; } printf("nthere %d prime(s)n",count); return 0; } |
现世难得能静下心来研究点东西