『算法-ACM 竞赛-数学-数论』质数处理

定义：
一个数的因数只有 1 和本身，那么这个数是质数。
质数的判断：
一个数 n 如果不是质数那么在 2—$sqrt(n)$一定有他的因子，于是：

bool isPrime (int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return false;
	}
	else return false;
}

但是在大量元素中，比如$1—1e6$中的质数，再用上面的朴素算法，就有些蹩脚了。
这里我们给出埃氏筛法：
原理：如果找到一个质数，那么这个质数的倍数都不是质数

int primes[N],cnt;
bool bprime[N];
void getPrime(int n){
    memset(bprime,false,sizeof(bprime));
    bprime[0]=true;
    bprime[1]=true;

    for(int i=2;i<=n;i++){
        if(!bprime[i]){
            prime[cnt++]=i;
            for(LL j=i*2;j<=n;j+=i)
                bprime[j]=true;
        }
    }
}

但是埃氏筛法的缺点：例如 6 会被 3 整除，6 会被 2 整除，会被筛两次，所以我们再给出欧氏线性筛法：

int primes[N],cnt;
bool bPrime[N];
void getPrimes(int n){
    memset(bPrime,false,sizeof(bPrime));

    for(int i=2;i<=n;i++){
        if(!bPrime[i])
            primes[cnt++]=i;

        for(int j=0;j<cnt&&i*primes[j]<n;j++){
            bPrime[i*primes[j]]=true;
            if(i%primes[j]==0)
                break;
        }
    }
}

1e8 以内的素数筛法

#include<iostream>
#include<bitset>
using namespace std;
bitset<100000010>v;
int prime[6000001];
int m=0;
void primes(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        if(!v[i])
        {
            for(int j=i*i; j<=n; j+=i)
                v[j]=1;
        }
    }
    for(int i=2; i<=n; i++)
        if(!v[i])
            prime[m++]=i;
    for(int i=0; i<m; i++)
        cout<<prime[i]<<endl;
}
int main()
{
    primes(1e3+20);
    return 0;
}

奇技淫巧：
用 6N±1 法求素数
任何一个自然数，总可以表示成为如下的形式之一：6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当 N≥1 时，6N，6N+2，6N+3，6N+4 都不是素数，只有形如 6N+1 和 6N+5 的自然数有可能是素数。所以，除了 2 和 3 之外，所有的素数都可以表示成 6N±1 的形式(N 为自然数)。

Miller-Rabin 算法
Miller-Rabin 算法是一个随机算法，随机生成几个 a 利用费马小定理与二次探测定理来检测素数。

只需要多次寻找不超过 n-1 基并检验是否有 ， 如果一直有， 那么这个数大概率就是一个素数，否则可以立即判定这个数是个合数。

虽然看似没有问题，但却存在一些数，对于 a 的某些选择可以骗过该算法，这些数虽然不是素数，但却对所有与 p 互素的 0<a<p 满足 ，因此，还需要附加二次探测定理的测试来改进不出错的几率。

LL Mult_Mod(LL a,LL b,LL m)//res=(a*b)%m
{
    a%=m;
    b%=m;
    LL res=0;
    while(b)
    {
        if(b&1)
            res=(res+a)%m;
        a=(a<<=1)%m;
        b>>=1;
    }
    return res%m;
}
LL Pow_Mod(LL a, LL b, LL m)//res=(a^b)%m
{
    LL res=1;
    LL k=a;
    while(b)
    {
        if((b&1))
            res=Mult_Mod(res,k,m)%m;

        k=Mult_Mod(k,k,m)%m;
        b>>=1;
    }
    return res%m;
}
bool Witness(LL a,LL n,LL x,LL sum)
{
    LL judge=Pow_Mod(a,x,n);
    if(judge==n-1||judge==1)
        return 1;

    while(sum--)
    {
        judge=Mult_Mod(judge,judge,n);
        if(judge==n-1)
            return 1;
    }
    return 0;
}
bool Miller_Rabin(LL n)
{
    if(n<2)
        return 0;
    if(n==2)
        return 1;
    if((n&1)==0)
        return 0;

    LL x=n-1;
    LL sum=0;
    while(x%2==0)
    {
        x>>=1;
        sum++;
    }


    int times=20;
    for(LL i=1;i<=times;i++)
    {
        LL a=rand()%(n-1)+1;//取与p互质的整数a
        if(!Witness(a,n,x,sum))//费马小定理的随机数检验
            return 0;
    }
    return 1;
}
int main()
{
    int p;
    cin>>p;

    if(Miller_Rabin(p))
        cout<<p<<"可能是素数"<<endl;
    else
        cout<<p<<"是合数"<<endl;

    return 0;
}