题目链接:
题意: 给出一个区间 [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 #include2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 7 const int MAXN = 1e6 + 10; 8 const int MAX = 1e5; 9 int prime[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.\n", x1 + l, y1 + l, x2 + l, y2 + l);59 }60 return 0;61 }