质数学习

· · 个人记录

参考《算法竞赛进阶指南》和网络（侵权联系删）

质数的判定

试除法:O(sqrt(N))

证明方法：反证
bool is_prime(int n){
    for(int i=2;i*i<=n;i++)
        if(n%i==0)return 0;
    return 1;
}

Eratopsthenes筛法:O(NloglogN)（接近线性）

void primes(int n){
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
        if(!v[i])
            for(int j=i+i;j<=n;j+=i)v[j]=1;
}

线性筛法（俗称：欧拉筛）:O(N)

相关知识：唯一分解定律
void primes(int n){
    memset(v,0,sizeof(v));
    m=0;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j=m;j++){
            if(prime[j]>v[i]||prime[j]>n/i)break;
            v[i*prime[j]]=prime[j];
        }
    }
}

Miller-Robbin（我不会）

浅谈 Miller-Robbin 与 Pollard Rho

质因数分解

试除法:接近O(sqrt(N))

void divide(){
    m = 0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            p[++m]=i;
            c[m]=0;
            while(n%i==0){
                n/=i;
                c[m]++;
            }
        }
    }
    if(m>1){
        p[++m]=m;
        c[m]=1;
    }
}

Polard's Rho(我也不会）

浅谈 Miller-Robbin 与 Pollard Rho

【学习笔记】Pollard's rho算法

质数算法略解

【例题】Prime Distance(POJ2689)

先用欧拉筛筛出1~sqrt(R)的质数
再同理Eratosthenes筛法，略有些不同，筛的范围L~R
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int maxR=2147483647,maxsqrt=50000;

long long v[50003],m,pri[50003],L,R,cnt,close,most,las,ans1,ans2,ans3,ans4;
long long start;
bool vis[1000003];

int main(){
    for(int i=2;i<=maxsqrt;i++){
        if(v[i]==0){
            v[i]=i;
            pri[m++]=i;
        }
        for(int j=0;j<m;j++){
            if(pri[j]>v[i]||pri[j]>maxsqrt/i)break;
            v[pri[j]*i]=pri[j];
        }
    }

    while(~scanf("%lld%lld",&L,&R)){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++){
            if(1ll*pri[i]*pri[i]>R)break;
            if(L%pri[i]==0)
                start=max(2ll,L/pri[i])*pri[i];else
                start=max(2ll,L/pri[i]+1)*pri[i];
            while(start<=R){
                vis[start-L]=1;
                start+=pri[i];
            }
        }

        cnt=most=las=0;
        close=maxR;
        for(int i=L;i<=R;i++)
            if(i>1&&!vis[i-L]){
                cnt++;
                if(las&&i-las>most){
                    most=i-las;
                    ans3=las;
                    ans4=i;
                }
                if(las&&i-las<close){
                    close=i-las;
                    ans1=las;
                    ans2=i;
                }
                las=i;
            }

        if(cnt<2)
            printf("There are no adjacent primes.\n");else
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",ans1,ans2,ans3,ans4);
    }

    return 0;
}