LOJ #143. 质数判定

题目描述

判定输入的数是不是质数。

输入格式

若干行，一行一个数 x。

行数不超过 1.5×10⁴。

输出格式

对于输入的每一行，如果 x 是质数输出一行 Y，否则输出一行 N。

样例

样例输入

样例输出

N

Y

N

N

Y

数据范围与提示

1≤x≤10¹⁸。

欢迎hack（如果你不是管理员，可以在题目讨论区发帖）。

Solution：

　　本题Miller-rabin模板题。

　　Miller-rabin其实是个很简单的算法，用来快速判断一个数是否为素数。

　　前置技能：二次探测定理。

　　　　若$a^2\equiv 1\mod p$且$p$为素数，则$a\equiv \pm 1\mod p$。

　　　　证明：$\because a^2\equiv 1\mod p$

　　　　 $\therefore (a+1)(a-1)\equiv 0 \mod p$

　　　　　　又$p$为素数

　　　　　　 $\therefore a=1$或$a=p-1$

　　我们由费马小定理，若$p$为素数，则$a^{p-1}\equiv 1 \mod p$，那么对于一个需要判断是否为素数的数$x$：

　　　　1、$x$必须是个非$1$的奇数。

　　　　2、令$x=2^k*c+1$（$c$为奇数），选择随机数$a$，使其满足所有$i<r$，都有$a^{2^i*c}\;mod\;p=p-1\;or\;1$。

　　然后就是模拟上述过程，多选几个随机数，若都能通过测试就是素数啦。

　　一般的话，随机选取4个数$2,3,5,7$，则在$2.5*10^{13}$以内唯一一个判断失误的数为$3215031751$。

　　然后细节就是当前数不能是所选取的随机数的倍数，否则会误判。

代码：

/*Code by 520 -- 9.10*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int cnt=,tab[]={,,,};

ll n,m;

ll Mul(ll x,ll y,ll mod){

    ll ans=(x*y-(ll)((long double)x/mod*y+0.5)*mod);

    return ans<?ans+mod:ans;

}

ll Exp(ll x,ll y,ll mod){

    ll ans=;

    while(y){

        if(y&) ans=Mul(ans,x,mod);

        y>>=;

        x=Mul(x,x,mod);

    }

    return ans;

}

bool Miller_Rabin(ll &n){

    if(n==||n==||n==||n==||n==||n==) return ;

    if(n==||n%==||n%==||n%==||n%==||n%==||n%==) return ;

    For(i,,cnt) {

        RE ll d=n-;

        while(!(d&)) d>>=;

        RE ll s=Exp(tab[i],d,n);

        while(s!=&&s!=n-&&d!=n-) d<<=,s=Mul(s,s,n);

        if(s!=n-&&!(d&)) return ;

    }

    return ;

}

int main(){

    while(scanf("%lld",&n)!=EOF) putchar(Miller_Rabin(n)?'Y':'N'),putchar('\n');

    return ;

}

巴特西