首页 > 其他 > 详细

米勒拉宾素数测试

时间:2016-02-14 12:57:41      阅读:955      评论:0      收藏:0      [点我收藏+]

  米勒拉宾素数测试可以快速测出单个数是否为素数。

  首先需要知道定理:

  1. 费马小定理: ap-1≡1(mod p)        其中p为质数

  于是,当有一个数n,先判断是不是1,2,3以及2,3的倍数(可以删掉大量数据),此时剩下的都是奇数。

  令n-1=2rd,取不同的a,对r从0到最大,满足ad≡1(mod n),此处要分情况。

  1)d为奇数,若同余1,可能为质数

  2)d为偶数,若同余-1,可能为质数

  3)循环后不符合上述情况,必为合数

 

  另外,对于取a的值,通常2,7,61就可计算至2^32数量级,若还需更大,则计算2,3,5,7,11.

  模板题hdu2138.

#include <cstdio>
int t,n,ans;
long long qpow(int x,int y,int mod)//快速幂
{
    long long ans=1,a=x;
    while(y)
    {
        if(y&1) ans=ans*a%mod;
        a=a*a%mod;
        y>>=1;
    }
    return ans;
}
bool MR_prime(int a,int n)//米勒拉宾
{
    int r=0,d=n-1;
    if(!(n%a)) return false;//倍数必为合数
    while(!(d&1))//找到奇数
    {
        d>>=1;
        r++;
    }
    long long k=qpow(a,d,n);
    if(k==1) return true;//同余1
    for(int i=0;i<r;i++,k=k*k%n) if(k==n-1) return true;//同余-1
    return false;
}
bool check_prime(int n)
{
    if(n==2||n==3||n==7||n==61) return true;
    if(!(n&1)||n%3==0||n==1) return false;//删掉大量已知情况
    if(MR_prime(2,n)&&MR_prime(7,n)&&MR_prime(61,n)) return true;
    return false;
}
int main()
{
    while(scanf("%d",&t)!=EOF)
    {
        ans=0;
        while(t--)
        {
            scanf("%d",&n);
            if(check_prime(n)) ++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

米勒拉宾素数测试

原文:http://www.cnblogs.com/cons/p/5188910.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!