题目 POJ2689 Prime Distance

原题传送门

主要思路

• 刚看到这题，心想：不就筛个 \(\left[2,U\right]\) 的质数表出来就可以了吗？一看数据范围： \(1<=L< U<=2147483647\) \(\cdots\) \(Woc\)，这 \(TM\) 可以做吗？看来必须另辟蹊径了。于是就有了下面这个做法。

• 显而易见，一个数 \(x\) 如果不是 \(prime\) ，则在 \(\left[2,\sqrt{x}\right]\) 中必有 \(x\) 的一个质因子。

• 因为 \(U-L<=1000000\) ，我们可以筛出 \(\left[2,\sqrt{U}\right]\) 的质数表，由这些质数，去将 \(\left[L,U\right]\) 中的合数筛除，那么在 \(\left[L,U\right]\) 中未被标记的便是 \(prime\) 了。

Code：

#include<cstdio>
#include<cmath>
#include<bitset>
#include<algorithm>
#include<cstring>
using namespace std;
#define rg register int
#define V inline void
#define I inline int
#define db double
#define B inline bool
#define ll long long
#define F1(i,a,b) for(rg i=a;i<=b;++i)
#define F3(i,a,b,c) for(rg i=a;i<=b;i+=c)
#define ed putchar('\n')
#define bl putchar(' ')
template<typename TP>V read(TP &x)
{
    TP f=1;x=0;register char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}
template<typename TP>V print(TP x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int N=1000005;
ll L,R;
ll pri[N],cnt,p[N],tot;
bitset<N>vis;
bool v[N];
template<typename TP>V make_prime_list(TP n)
{
    F1(i,2,n)
    {
        if(!vis[i]) pri[++cnt]=i;
        for(TP j=1;j<=cnt && pri[j]*i<=n;++j)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
//  freopen("1.txt","w",stdout);
    while(~scanf("%lld%lld",&L,&R))
    {
        vis.reset();memset(v,0,sizeof v);
        cnt=tot=0;
        if(L==1) ++L;
        make_prime_list((int)sqrt(R)+1);
        F1(i,1,cnt)
            for(ll j=L/pri[i];j*pri[i]<=R;++j)
                if(j>1) v[j*pri[i]-L]=1;
        F1(i,0,R-L)
            if(v[i]==0) p[++tot]=i+L;
        if(tot<=1) puts("There are no adjacent primes.");
        else
        {
            rg maxx=0,minx=N,posx=-1,posy=-1;
            F1(i,2,tot)
            {
                if(p[i]-p[i-1]>maxx) maxx=p[i]-p[i-1],posy=i-1;
                if(p[i]-p[i-1]<minx) minx=p[i]-p[i-1],posx=i-1;
            }
            if(posx==-1 || posy==-1) puts("There are no adjacent primes.");
            else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p[posx],p[posx+1],p[posy],p[posy+1]);
        }
    }
}