POJ-2689 Prime Distance(区间素数筛--经典题)
题意：
给出一个区间[L, R]，求该区间内的所有素数(1 <= L,R <= 2.1E9, R-L <= 1e6)
思路：
区间素数筛，枚举不超过sqrt(R)的所有质数p，然后再去枚举[L, R]区间内p的倍数，将之划去，最后区间内剩下的就都是素数了。注意一点，1需要特判不是素数。
代码：
#include <algorithm>
#include <string.h>
#include <cstdio>
#define LL long long
using namespace std;
const int N = 1e5;
const int maxn = 1e6+5;
int isprime[maxn], prime[maxn], len;
LL L, R;
int ans[maxn];
void prime_init()
{
len = 0;
memset(isprime, 0, sizeof isprime);
for(int i = 2; i <= N; ++i)
if(!isprime[i])
{
prime[++len] = i;
if(1ll*i*i > N) continue;
for(int j = i*i; j <= N; j+=i)
isprime[j] = 1;
}
}
void work()
{
memset(ans, 0, sizeof ans);
for(int i = 1; i <= len; ++i)
{
if(1ll*prime[i]*prime[i] > R) break;
LL star = ((L-1)/prime[i]+1)*prime[i];
for(LL j = star; j <= R; j+=prime[i])
if(j != prime[i]) ans[j-L+1] = 1;
}
if(L == 1) ans[1] = 1;
}
int main()
{
prime_init();
while(~scanf("%lld %lld", &L, &R))
{
work();
LL i, mins, maxx, ans1, ans2, ans3, ans4;
ans1 = ans2 = -1, i = 0;
while(i < R-L+1 && (ans1 == -1 || ans2 == -1))
{
++i;
if(ans[i]) continue;
if(ans1 == -1) ans1 = i+L-1;
else if(ans2 == -1) ans2 = i+L-1;
}
if(ans1 == -1 || ans2 == -1) puts("There are no adjacent primes.");
else
{
mins = maxx = ans2-ans1;
ans3 = ans1, ans4 = ans2;
int pre = ans2;
for(++i; i <= R-L+1; ++i)
{
if(ans[i]) continue;
if(i+L-1-pre < mins)
{
mins = i+L-1-pre;
ans1 = pre, ans2 = i+L-1;
}
if(i+L-1-pre > maxx)
{
maxx = i+L-1-pre;
ans3 = pre, ans4 = i+L-1;
}
pre = i+L-1;
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n", ans1, ans2, ans3, ans4);
}
}
return 0;
}
继续加油~