题目 POJ2689 Prime Distance

[原题传送门](http://poj.org/problem?id=2689)

主要思路

刚看到这题，心想：不就筛个 \(\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：

```cpp
#include
#include
#include
#include
#include
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;iV read(TP &x)
{
TP f=1;x=0;register char c=getchar();
for(;c>'9'||c='0'&&cV print(TP x)
{
if(x9) print(x/10);
putchar(x%10+'0');
}
const int N=1000005;
ll L,R;
ll pri[N],cnt,p[N],tot;
bitsetvis;
bool v[N];
templateV make_prime_list(TP n)
{
F1(i,2,n)
{
if(!vis[i]) pri[++cnt]=i;
for(TP j=1;j1) v[j*pri[i]-L]=1;
F1(i,0,R-L)
if(v[i]==0) p[++tot]=i+L;
if(totmaxx) maxx=p[i]-p[i-1],posy=i-1;
if(p[i]-p[i-1]

巴特西

POJ2689

题目 POJ2689 Prime Distance

主要思路

Code：

最新文章

热门文章