Miller-Rabinランダム素数テストアルゴリズム

大物ブログ個人比較料理は板を使えばいいです.例題hdu 2138暴力はできるが、アルゴリズムを学ぶために使いましょう.

#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=1e6+10;
int S;//       ，         
LL quick_mod_multi(LL a,LL b,LL mod)//   a*b%mod
{
    LL t=0;
    a%=mod;
    while(b)
    {
        if(b&1) t=(t+a)%mod;
        a=(a<<1)%mod;
        b>>=1;
    }
    return t;
}
LL quick_mod_power(LL a,LL b,LL mod)//   a^b%mod
{
    LL res=1;
    a%=mod;
    while(b)
    {
        if(b&1)
        res=quick_mod_multi(res,a,mod);
        b>>=1;
        a=quick_mod_multi(a,a,mod);
    }
    return res;
}
bool miller_rabbin(LL n)//    
{
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    int t=0;
    LL a,x,y,u=n-1;
    while((u&1)==0) t++,u>>=1;
    srand((unsigned)time(NULL));
    for(int i=0;i//     
    {
        a=rand()%(n-1)+1;
        x=quick_mod_power(a,u,n);
        for(int j=0;jif(y==1&&x!=1&&x!=n-1)
                return false;
            x=y;
        }
        if(x!=1) return false;
    }
    return true;
}
int main()
{
    S=3;
    int n;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(int i=0;iscanf("%lld",&a);
            if(miller_rabbin(a)) sum++;
        }
        printf("%d
",sum);
    }
}

ここには暴力よりも速いアルゴリズムがあり、素数にこのような法則があることを発見したばかりだ.

#include
#include
int pr[8]={4,2,4,2,4,6,2,6};//  7         （    or       ），     200     
int prime(int n)
{
    int i=7,j;
    if(n<2)
        return 0;
    if(n==2||n==3||n==5)
        return 1;
    if(!(n%2&&n%3&&n%5))
        return 0;
    for(;i<=sqrt(n);)
    {
        for(j=0;j<8;j++)
        {
            if(n%i==0)
             return 0;
            i+=pr[j];
        }
        if(n%i==0)
         return 0;
    }
    return 1;
}
int main()
{
    int i,n,m,s;
    while(scanf("%d",&n)!=EOF)
    {
        s=0;
        for(i=0;i"%d",&m);
            if(prime(m))
                s++;
        }
        printf("%d
",s);
    }
    return 0;
}