我之前写到过 欧拉筛 埃氏筛 按其复杂度来说 到 1e6是完全可以的,but 如果让你筛选 区间[a,b]的素数(b-a)<=1e6,但a,b最大值为1e11,你怎么办呢.欧拉筛 埃氏筛

首先不要慌 ,一步一步来,a,b最大值为 1e11,但我们知道 用 sqrt(b) 之前的素数 可以筛选1e11的素数

所以我们将 1e6之前的素数 事先打表,然后用这些素数去筛 [a,b]区间内哪些不是素数

但a,b区间太大了,无法开,但b-a<=1e6,所以 我们将区间偏移至 [0,b-a],这样我就可以控制了

外层循环1e6之前的素数,内层用埃氏筛法改进,找到第一个大于a的 且为当前枚举的素数 的倍数的数,然后每次+当前枚举的prime,因为这是prime的倍数,所以他不是素数.(但最少2倍以上,代码中有细节)直接标记就好了 具体怎么区间转移看一下代码就好了:

        for(int i=1;i<=cnt;i++)//外层1e6以内的素数
        {
            ll x=prime[i];
            for(ll k=max(2ll,(n+x-1)/x)*x;k<=m;k+=x)// (n+x-1)/x 是至少为x几倍 注释①
                    other[k-n]=false;
        }

注释①:这个证明详见:证明

然后我们遍历 :

        for(ll i=n;i<=m;i++)
            if(other[i-n]) save[++cnt1]=i;

save里就可以存起来了.

放一道例题叭: POJ 2689 Prime Distance

题目大意:输出a,b区间内,相邻最近的两个素数,与相邻最远的两个素数

题目思路:我们把区间a,b内的素数都找出来,然后遍历一遍差值就可以了

AC:

//#include <bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define E 2.718
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll INF=1e9+7;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll prime[maxn];
bool vis[maxn];
bool other[maxn];
ll save[maxn];
ll temp[maxn];
ll cnt=0;
void inint()
{
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<50000;i++)
    {
        if(vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<50000;k+=i)
                vis[k]=false;
        }
    }
}
int main()
{
    inint();
    while(~scanf("%lld%lld",&n,&m))
    {
        ll cnt1=0;
        memset(other,true,sizeof(other));
        if(n==1) other[0]=false;
        for(int i=1;i<=cnt;i++)
        {
            ll x=prime[i];
            for(ll k=max(2ll,(n+x-1)/x)*x;k<=m;k+=x)
                    other[k-n]=false;
        }
        for(ll i=n;i<=m;i++)
            if(other[i-n]) save[++cnt1]=i;
        if(cnt1<=1) printf("There are no adjacent primes.\n");
        else
        {
            for(ll i=2;i<=cnt1;i++)
                temp[i]=save[i]-save[i-1];
            ll maxl=-INF,minl=INF;
            int pos=-1,pos1=-1;
            for(int i=2;i<=cnt1;i++)
            {
                if(temp[i]>maxl)
                {
                    maxl=temp[i];
                    pos=i;
                }
                if(temp[i]<minl)
                {
                    minl=temp[i];
                    pos1=i;
                }
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",save[pos1-1],save[pos1],save[pos-1],save[pos]);
        }
    }
    return 0;
}

总结:Get New Knowledge !