poj2689 Prime Distance 有难度 埃拉托斯尼斯筛法的运用

时间:2024-07-04 23:04:08

我承认这道很难(对我来说),搞脑子啊,搞了好久,数论刚开始没多久,还不是很强大,思路有点死,主要是我 天赋太差,太菜了,希望多做做有所改善

开始解析:

首先要将在 [ l,u]内的所有素数找出来,还好题目说了u-l 小于 1000 000,不然内存都得暴死了,最常用的方法就是筛法了,当然还有 传说中的 6*n+1 可惜我不会,

开始假设所有范围内的数都是素数,然后讲所有素数的倍数(肯定不是素数)筛掉,经过无数轮的筛选,余下的就是素数,同时要考虑到所有大于2的偶数都不是素数,可以节省空间,

使用筛法筛掉[l,u]内的所有非素数,需要知道[l,u]的所有非素数的素因子(因为一个非素数是被它最小的素因子删掉的),2 147 486 647内的数或者是素数,或者能呗根号(2 147 486 647)内的素数正数,也就是说,[l,u]区间的所有非素数的素因子都在 根号(2 147 486 647)内;

预先将 根号(2 147 483 647)内的所有素数都找出来,然后用这些素数去筛掉指定区间内的所有非素数,

要考虑到 素数定理来确定做题的范围, n/lnn就是最多的素数个数


#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set> #define ll long long
#define LL __int64
#define eps 1e-8
#define e 2.718281828
//
//const ll INF=9999999999999; #define M 400000100 #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;
//
//vector<int>G[30012]; bool isprime[50012*20];
ll prime1[50012],prime2[1000012];
ll l,u;
ll numofprime1,numofprime2;//宁可写复杂点也要表达明确意思不误导自己 void dopprime()//筛法,就是模版,直接套上去,注意自己选定的范围,n/lnn
{
memset(isprime,true,sizeof(isprime));
isprime[1]=0;
numofprime1=0;
for(ll i=2;i<=50012;i++)
{
if(isprime[i])
{
prime1[++numofprime1]=i;
for(ll j=i*i;j<50001;j+=i)
isprime[j]=false;
}
}
} void dopprime2()//来筛区间内的非素数
{
ll tmp;
memset(isprime,true,sizeof(isprime));
for(ll i=1;i<=numofprime1;i++)
{
tmp=l/prime1[i];
while(tmp*prime1[i] < l || tmp <= 1)
tmp++;
for(ll j=tmp*prime1[i];j<=u;j+=prime1[i])
{
if(j >= l)
isprime[j-l]=false;
}
}
if(l==1)
isprime[0]=false;
} int main(void)
{
dopprime();//筛法
while(~scanf("%lld %lld",&l,&u))
{
dopprime2();
numofprime2=0;
ll minn=inf,maxn=-inf;
ll minl,minr,maxl,maxr;
for(ll i=0;i<=u-l;i++)
if(isprime[i])
prime2[++numofprime2]=i+l;
if(numofprime2 <= 1)
{
printf("There are no adjacent primes.\n");
continue;
}
for(ll i=1;i<numofprime2;i++)//找相邻的方法,很简单,但是我居然写错了刚开始
{
if(prime2[i+1]-prime2[i] < minn)
{
minn=prime2[i+1]-prime2[i];
minl=prime2[i];
minr=prime2[i+1];
}
if(prime2[i+1]-prime2[i] > maxn)
{
maxn=prime2[i+1]-prime2[i];
maxl=prime2[i];
maxr=prime2[i+1];
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minl,minr,maxl,maxr);
}
}