大意不再赘述。
思路:本题数据区间的上下界到达21亿,所以数组是存不下来的。只能针对本题的假设:区间的长度小于1000000,然后把区间[L,U]内的素数筛选出来。
具体怎么去筛选,我们知道,2147483647内的数要么是素数,要么可以被sqrt(2147483647)内的素数整除,也就是说,[L,U]区间内所有的非素数的所有素数因子都在sqrt(2147483647)内。
首先将sqrt(2147483647)所有的素数筛选出来,然后用这些素数去筛选区间[L,U]内的非素数。
注意一些细节问题,如把is_prime[0] = 1,因为1不是素数。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long LL; const int MAXN = 46341; //(int)sqrt(INT_MAX+0.5)+1; const int INF = 0x3f3f3f3f; LL L, U; bool vis[MAXN]; int prime[MAXN]; int tot1; bool is_prime[1000010]; LL prime2[1000010]; int tot2; void init() { tot1 = 0; memset(vis, 0, sizeof(vis)); for(LL i = 2; i < MAXN; i++) if(!vis[i]) { prime[tot1++] = i; for(LL j = i*i; j < MAXN; j += i) vis[j] = 1; } } void do_prime() { memset(is_prime, 0, sizeof(is_prime)); for(int i = 0; i < tot1; i++) { LL b = L / prime[i]; while(b * prime[i] < L || b <= 1) b++; //1、取在L的右边,离L最近的非素数。2、L本身在已经预处理出来的素数的范围内。 for(LL j = b * prime[i]; j <= U; j += prime[i]) { if(j >= L) is_prime[j-L] = 1; } } if(L == 1) is_prime[0] = 1; //L为1时的边界 tot2 = 0; for(LL i = 0; i <= U-L; i++) if(!is_prime[i]) { prime2[tot2++] = i+L; } } void solve() { init(); do_prime(); if(tot2 <= 1) { printf("There are no adjacent primes.\n"); return ; } LL min = INF, max = -INF, minl = 0, minr = 0, maxl = 0, maxr = 0; for(int i = 1; i < tot2; i++) { LL dif = prime2[i] - prime2[i-1]; if(min > dif) { min = dif; minl = prime2[i-1], minr = prime2[i]; } if(max < dif) { max = dif; maxl = prime2[i-1], maxr = prime2[i]; } } printf("%lld,%lld are closest, %lld,%lld are most distant.\n", minl, minr, maxl, maxr); } int main() { while(~scanf("%lld%lld", &L, &U)) { solve(); } return 0; }