题解 P1835 【素数密度_NOI导刊2011提高（04）】

· · 题解

加速版 (简化版) Miller_Rabin

只用费马小定理,即当p \in prime时,\ \ \ a^{p-1} \equiv 1 (mod \ p)

所以随机在[1,p-1]选一个正整数赋给a

用费马小定理测试,

当p \in prime时,上述式子一定成立

当p \notin prime时,上述式子只有 25\% 的可能性成立

所以多试几次就好了,试10次就足以保证正确性了

测试失败的概率小到4^{-10}

并且省去了很多骤!

很短--->

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int l,r,ans;
ll qpow(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
bool Miller(ll x){
    if(x==2)return true;
    if(x==1||!(x&1))return false; 
    for(int i=0;i<10;i++){
        ll a=rand()%(x-1)+1;
        if(qpow(a,x-1,x)^1)return false;
    } 
    return true;
}
int main(){
    srand(time(0));
    l=read(),r=read();
    for(register ll i=l;i<=r;++i){
        if(Miller(i))++ans;
    }
    printf("%d\n",ans);
    return 0;
}

Froggy's blog

呱!!