摘要：
a:b;24}2526intmain{27get_prime();28lll,r;29while{30memset;31for{32lla=/prime[i];33llb=r/prime[i];34for{//筛[l,r]内的合数35vis[prime[i]*j-l]=1;//减个l方便标记,输出答案时加回去即可36}37}38ifvis[0]=1;//注意这个1并不是素数39llcnt=-1,sol1=MAXN,sol2=0,x1,y1,x2,y2;40for{41if{42if(cnt!
题意: 给出一个区间 [l, r] 求其中相邻的距离最近和最远的素数对 . 其中 1 <= l < r <= 2,147,483,647, r - l <= 1e6 .
思路: 素数区间筛
要找到 [l, r] 中相邻最近和最远的素数对肯定是需要找出 [l, r] 内所有素数 . 但是无论是直接线性打表还是暴力都处理不了这么大的数据 .
可以先给 sqrt(r) 内的素数打个表, 再用 sqrt(r) 内的素数去筛选 [l, r] 内的合数, 然后再遍历一次 [l, r], 记录答案即可 .
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define ll long long 5 using namespacestd; 6 7 const int MAXN = 1e6 + 10; 8 const int MAX =1e5; 9 intprime[MAX], tag[MAX], vis[MAXN], tot; 10 11 void get_prime(void){ 12 for(int i = 2; i < MAX; i++){ 13 if(!tag[i]){ 14 prime[tot++] =i; 15 for(int j = 2; j * i < MAX; j++){ 16 tag[j * i] = 1; 17 } 18 } 19 } 20 } 21 22 ll Max(ll a, ll b){ 23 return a > b ?a : b; 24 } 25 26 int main(void){ 27 get_prime(); 28 ll l, r; 29 while(~scanf("%lld%lld", &l, &r)){ 30 memset(vis, 0, sizeof(vis)); 31 for(int i = 0; i < tot; i++){ 32 ll a = (l + prime[i] - 1) /prime[i]; 33 ll b = r /prime[i]; 34 for(int j = Max(2, a); j <= b; j++){ //筛[l, r]内的合数 35 vis[prime[i] * j - l] = 1; //减个l方便标记,输出答案时加回去即可 36 } 37 } 38 if(l == 1) vis[0] = 1; //注意这个1并不是素数 39 ll cnt = -1, sol1 = MAXN, sol2 = 0, x1, y1, x2, y2; 40 for(int i = 0; i <= r - l; i++){ 41 if(vis[i] == 0){ 42 if(cnt != -1){ 43 if(sol1 > i -cnt){ 44 x1 =cnt; 45 y1 =i; 46 sol1 = i -cnt; 47 } 48 if(sol2 < i -cnt){ 49 x2 =cnt; 50 y2 =i; 51 sol2 = i -cnt; 52 } 53 } 54 cnt =i; 55 } 56 } 57 if(sol2 == 0) puts("There are no adjacent primes."); 58 else printf("%lld,%lld are closest, %lld,%lld are most distant. ", x1 + l, y1 + l, x2 + l, y2 +l); 59 } 60 return 0; 61 }