素数的判断（大数据，大规模）

素数的判断其实谁都会，所以这篇跳过简单的素数判断，直接学习如何快速判断1到N的素数，以及判断大数据是否为素数。

 1)埃氏筛法

现在我们先学习埃氏筛选法，此法实用与大规模判断素数，比如1到N的素数有那些啊，等等等等。

这个算法流弊哦，与辗转相除法一样古老哇。

首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数，将表中2的倍数都划去。表中剩余的最小数字是3，不能被更小的数整除，是素数。如果表中最小的是m，m为素数，将m的倍数划去。

 附上表格学习：

2	3	4	5	6	7	8	9	10	11	12
2	3	–	5	–	7	–	9	–	11	–
2	3	–	5	–	7	–	–	–	11	–

#include<stdio.h>
#define MAX 1000000
bool is[MAX];///判断
int pr[MAX];///储存素数
///返回1到n有多少个素数，以及储存
int sieveint n)
{
    int p=0;
    ///初始化让他们高兴一下先
    forint i=0 ; i<=n ;i++)
        is[i]=true;
        is[0]=is[1]=false;///根本都不是自己人
        forint i=2 ; i<=n ; i++)
        {
            ///如果是自己人
            ifis[i])
            {
                ///我就记录咯
                pr[++p]=i;
                ///那现在就很明显了，关于自己人I的倍数都不是自己人了
                forint j=i*2 ; j<=n ; j+=i)
                    is[j]=false;
            }
        }
        return p;
}
int main)
{
    int n;
    scanf"%d",&n);
    printf"%d
",sieven));
    return 0;
}

View Code

往往题目不会那么简单，现在来搞一个难一点的区间筛法哼哼。。。。

求区间[a,b]内的素数个数，哇哈哈哈。

b以内的合数一定不会超过根号b，如果有根号b以内的素数表的话，那我们就可以把它运用到（a,b]上。也就是说我们要先搞出[ 2 ，根号b] 的表与[ a , b ]的表，然后在从[ 2 , 开B ]的表中筛选出素数的同时，也将其倍数在[ a , b ]的表中划去，流弊吧。

#include<stdio.h>
#define MAX 1000007
#define ll long long
bool issmall[MAX];///[2,sqrtb]
bool is[MAX];///[a,b]
void segll a,ll b)
{
    ll i,j;
    ///对[2,sqrtb))的初始化全为质数
    for i=0 ; i*i<b ; i++)
        issmall[i]=true;
    ///对下标偏移后的[a,b)进行初始化
    for i=0 ; i<b-a ; i++)
        is[i]=true;
        ///在筛选[2,sqrtb)],在筛选这个区间的同时，将大区间的也搞了
    for i=2 ; i*i<b ; i++)
    {
        ifissmall[i])
        {
            for j=2*i ; j*j<b ; j+=i)
                issmall[i]=false;///不是自己人
             ///a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
            for j=a+i-1)/i*i ; j<b ;j+=i )
                is[j-a]=false;
        }
    }
}
int main)
{
    ll a,b;
    whilescanf"%lld%lld",&a,&b)!=EOF)
    {
        sega,b);
        ll cnt=0;
        forll j=0 ; j<b-a ; j++)
        {
            ifis[j])
            {
                cnt++;
            }
        }

        ifa==1)
            cnt--;
        printf"%d
",cnt);
    }
}

View Code

素不素很流弊勒，现在来实战下；

题意：给定两个素数n和m，要求把n变成m，每次变换时只能变一个数字，即变换后的数与变换前的数只有一个数字不同，并且要保证变换后的四位数也是素数。求最小的变换次数；如果不能完成变换，输出Impossible。

无论怎么变换，个位数字一定是奇数（个位数字为偶数肯定不是素数），这样枚举个位数字时只需枚举奇数就行；而且千位数字不能是0。所以可以用广搜，枚举各个数位上的数字，满足要求的数就加入队列，直到变换成功。因为是广搜，所以一定能保证次数最少。

AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

int n, m;
const int N = 1e4 + 100;
int vis[N];
struct node
{
    int x, step;
};
queue<node> Q;

bool judge_primeint x) //判断素数
{
    ifx == 0 || x == 1)
        return false;
    else ifx == 2 || x == 3)
        return true;
    else
    {
        forint i = 2; i <= int)sqrtx); i++)
            ifx % i == 0)
                return false;
        return true;
    }
}

void BFS)
{
    int X, STEP, i;
    while!Q.empty))
    {
        node tmp;
        tmp = Q.front);
        Q.pop);
        X = tmp.x;
        STEP = tmp.step;
        ifX == m)
        {
            printf"%d
",STEP);
            return ;
        }
        fori = 1; i <= 9; i += 2) //个位
        {
            int s = X / 10 * 10 + i;
            ifs != X && !vis[s] && judge_primes))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.pushtemp);
            }
        }
        fori = 0; i <= 9; i++) //十位
        {
            int s = X / 100 * 100 + i * 10 + X % 10;
            ifs != X && !vis[s] && judge_primes))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.pushtemp);
            }
        }
        fori = 0; i <= 9; i++) //百位
        {
            int s = X / 1000 * 1000 + i * 100 + X % 100;
            ifs != X && !vis[s] && judge_primes))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.pushtemp);
            }
        }
        fori = 1; i <= 9; i++) //千位
        {
            int s = i * 1000 + X % 1000;
            ifs != X && !vis[s] && judge_primes))
            {
                vis[s] = 1;
                node temp;
                temp.x = s;
                temp.step = STEP + 1;
                Q.pushtemp);
            }
        }
    }
    printf"Impossible
");
    return ;
}

int main)
{
    int t, i;
    scanf"%d",&t);
    whilet--)
    {
        while!Q.empty)) Q.pop);
        scanf"%d%d",&n,&m);
        memsetvis,0,sizeofvis));
        vis[n] = 1;
        node tmp;
        tmp.x = n;
        tmp.step = 0;
        Q.pushtmp);
        BFS);
    }
    return 0;
}

View Code

（2）埃氏的优化，依拉筛法

我们可以知道，任意一个正整数k，若k≥2，则k可以表示成若干个质数相乘的形式。Eratosthenes筛法中，在枚举k的每一个质因子时，我们都计算了一次k，从而造成了冗余。因此在改进算法中，只利用k的最小质因子去计算一次k。 
与Eratosthenes筛法不同的是，对于外层枚举i，无论i是质数，还是是合数，我们都会用i的倍数去筛。但在枚举的时候，我们只枚举i的质数倍。比如2i,3i,5i,…，而不去枚举4i,6i…，原因我们后面会讲到。

此外，在从小到大依次枚举质数p来计算i的倍数时，我们还需要检查i是否能够整除p。若i能够整除p，则停止枚举。

利用该算法，可以保证每个合数只会被枚举到一次。

综上，Eular筛法可以保证每个合数只会被枚举到一次，时间复杂度为On)。当N越大时，其相对于Eratosthenes筛法的优势也就越明显。

AC代码：

int primelist[N], primecount = 0;
bool isprime[N];
void eularint n){
    int i, j;
    for i = 0; i <= n; i++){
        isprime[i] = true;
    }
    isprime[0] = isprime[1] = false;
    for i = 2; i <= n; i++){
        if isprime[i]){
            primelist[primecount++] = i;
        }
        for j = 0; j < primecount; j++){
            if i*primelist[j] > n){
                break;
            }
            isprime[i*primelist[j]] = false;
            if i%primelist[j]==0){
                break;
            }
        }
    }
}

View Code

（3）大数据打表法

#include<stdio.h>
#include<math.h>
int p[1000000],a[10000001],t=0;
int primeint n)
{
    int i,q;
    q=int)sqrtn);
    fori=0;p[i]<=q&&t;i++)
        ifn%p[i]==0)return 0;
    return 1;
}
void main)
{
    int n,i;
    scanf"%d",&n);
    fori=2;i<=n;i++)
        ifprimei))p[t++]=i;
    fori=0;i<t;i++)
        printf"%d%c",p[i],i<t-1?' ':'/n');
}

View Code

（4）神奇万能法

适合单数据，也适合超大数据

#include<stdio.h>
#include<math.h>
int p[8]={4,2,4,2,4,6,2,6};
int primeint n)
{
    int i=7,j,q;
    ifn==1)return 0;
    ifn==2||n==5||n==3)return 1;
    ifn%2==0||n%3==0||n%5==0)return 0;
    q=int)sqrtn);
    for;i<=q;){
        forj=0;j<8;j++){
            ifn%i==0)return 0;
            i+=p[j];
        }
        ifn%i==0)return 0;
    }
    return 1;
}
void main)
{
    int n;
    scanf"%d",&n);
    ifprimen))puts"Yes");
    else puts"No");
}

View Code

 
大素数测试+求最小素因子+最大素因子（模版）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAXN 10
#define C 16381
using namespace std;
typedef __int64 I64;
 
I64 min;
 
I64 multiI64 a, I64 b, I64 n){
    I64 tmp = a % n, s = 0;
    whileb){
        ifb & 1) s = s + tmp) % n;
        tmp = tmp + tmp) % n;
        b >>= 1;
    }
    return s;
}
 
I64 PowI64 a, I64 b, I64 n){
    I64 tmp = a % n, s = 1;
    whileb){
        ifb & 1) s = multis, tmp, n);
        tmp = multitmp, tmp, n);
        b >>= 1;
    }
    return s;
}
 
int witnessI64 a, I64 n){
    I64 u = n - 1, t = 0, i, x, y;
    while!u & 1))    u >>= 1, t ++;
    x = Powa, u, n);
    fori = 1; i <= t; i ++){
        y = multix, x, n);
        ify == 1 && x != 1 && x != n -1) return 1;
        x = y;
    }
    ifx != 1) return 1;
    return 0;
}
 
int testI64 n){
    I64 a;
    int i;
    ifn == 2) return 1;
    ifn < 2 || !n & 1)) return 0;
    srandI64)time0));
    fori = 0; i < MAXN; i ++){
        a = I64) rand)) % n - 2) + 2;
        ifwitnessa, n)) return 0;
    }
    return 1;
}
 
I64 gcdI64 a, I64 b){
    return b ? gcdb, a % b) : a;
}
 
I64 pollard_rhoI64 n, I64 c){
    I64 x, y, d, i = 1, k = 2;
    srandI64)time0));
    x = I64) rand)) % n - 1) + 1;
    y = x;
    while1){
        i ++;
        x = multix, x, n) + c) % n;
        d = gcdy - x + n, n);
        ifd != 1 && d != n) return d;
        ify == x) return n;
        ifi == k) y = x, k <<= 1;
    }
}
 
void findI64 n, I64 c){
    I64 r;
    ifn <= 1) return;
    iftestn)){
        ifmin > n) min = n;
        return;
    }
    r = pollard_rhon, c--);
    findn / r, c);
    findr, c);
}
 
I64 MaxPrimeFactorI64 n)
{
    iftestn))
    return n;
    
    I64 k=-1,g;
    min=n;
    findn,C);
    
    g=MaxPrimeFactormin);
    k=g>k?g:k;
    
    g=MaxPrimeFactorn/min);
    k=g>k?g:k;
    return k;
}
int main){
    I64 n;
        while~scanf"%I64d", &n))
        {
            // iftestn)){                //testn)测试n是不是素数
            // printf"Prime
");
            // continue;
            // }
            // min = n;                   //min表示n的最小素因子
            // findn, C);                //找出n的最小素因子
            // printf"%I64d
",min);
            printf"%I64d
",MaxPrimeFactorn));//求n的最大素因子
        }
    return 0;
}

View Code