[POJ 2689] Prime Distance【欧拉筛】
Problem:
Time Limit: 1000MS | Memory Limit: 65536K |
Description
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Input
Output
Sample Input
2 17 14 17
Sample Output
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
Source
Solution:
用线性筛筛出 [2, sqrt(maxInt)] 上的素数,并同时维护出 [L, U] 上的素数(在数组 isrprm[] 中时将坐标偏移 -L 保存)。
注意以下几点:
- 用 long long 存储防止累加溢出。
- 当 L == 1 时,防止将 1 当作素数处理。
Code: O(TR), 其中R=10^6 [1236K, 125MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const ll maxInt = 1000000007; ll prm[25005]; int prmSize; bool isprm[50005]; ll L, U; bool isrprm[1000005]; inline void calcPrime(){ memset(isprm, 1, sizeof(isprm)); memset(isrprm, 1, sizeof(isrprm)); isprm[0] = isprm[1] = 0, prmSize = 0; if(L == 1) isrprm[0] = 0; // Beware of the ignorance of regarding 1 as a prime!!! for(register int i = 2; i <= 50000; i++){ if(isprm[i]) prm[++prmSize] = i; for(register int j = 1; j <= prmSize && i * prm[j] <= 50000; j++){ isprm[i * prm[j]] = 0; if(i % prm[j] == 0) break; // The core of Euler's Sieve } // Primes below sqrt(maxInt) are enough for(register ll j = i * max(2LL, (L - 1) / i + 1); j <= U; j += i) isrprm[j - L] = 0; // Update primes in [L, U] synchronously, using "long long" to avoid overflowing } } int main(){ while(scanf("%lld%lld", &L, &U) != EOF){ calcPrime(); pair<ll, ll> cls(-maxInt, maxInt), dst(-maxInt, -maxInt); // Record the answers ll prev = -1; for(register ll i = L; i <= U; i++){ if(!isrprm[i - L]) continue; if(prev != -1){ if(i - prev < cls.second - cls.first) cls.second = i, cls.first = prev; if(i - prev > dst.second - dst.first) dst.second = i, dst.first = prev; } prev = i; } if(cls.first == -maxInt) puts("There are no adjacent primes."); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n", cls.first, cls.second, dst.first, dst.second); } return 0; }
发表评论