Prime Distance
The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers. 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
Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.
Output
For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.
Sample Input
2 17
14 17
Sample Output
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
Source
题目类型：素数筛法
算法分析：由于问题的规模比较大，不可能将所有的范围内的素数都打表出来，只能将1~sqrt (2 ^ 31 - 1)内的素数先打表出来，然后再对于每个给定的区间(区间长度小于1000000)筛出素数，然后对于打出的素数表，遍历一次并维护相邻两个素数的最大值(和两个下标)和最小值(和两个下标)即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 50000 + 66; bool prime[maxn*20]; long long primelist[maxn], prime_len; long long primelist2[maxn*20], prime_len2; void GetPrime () { memset (prime, true, sizeof (prime)); prime_len = 0; long long i; for (i = 2; i <= maxn; i++) { if (prime[i]) primelist[prime_len++] = i; long long j; for (j = 0; j < prime_len; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } void Solve (long long a, long long b) { memset (prime, true, sizeof (prime)); for (long long i = 0; i < prime_len; i++) { long long temp = a / primelist[i]; while (temp * primelist[i] < a || temp <= 1) temp++; for (long long j = temp * primelist[i]; j <= b; j += primelist[i]) { if (j >= a) prime[j-a] = false; } } if (a == 1) prime[0] = false; prime_len2 = 0; for (long long i = a; i <= b; i++) { if (prime[i-a]) primelist2[prime_len2++] = i; } } int main() { GetPrime (); // freopen ("aaa.txt", "r", stdin); long long a, b; while (scanf ("%lld%lld", &a, &b) != EOF) { Solve (a, b); if (prime_len2 < 2) printf ("There are no adjacent primes.\n"); else { long long minval = INF, maxval = -INF, minval_a = -1, minval_b = -1, maxval_a = -1; long long maxval_b = -1; for (long long i = 1; i < prime_len2; i++) { if (minval > primelist2[i] - primelist2[i-1]) { minval = primelist2[i] - primelist2[i-1]; minval_a = primelist2[i-1], minval_b = primelist2[i]; } if (maxval < primelist2[i] - primelist2[i-1]) { maxval = primelist2[i] - primelist2[i-1]; maxval_a = primelist2[i-1], maxval_b = primelist2[i]; } } printf ("%lld,%lld are closest, %lld,%lld are most distant.\n", minval_a, minval_b , maxval_a, maxval_b); } } return 0; } |
- « 上一篇：poj2585
- poj2709：下一篇 »