题目链接：传送门
Sample Input
代码语言：javascript复制2 17
14 17Sample Output
代码语言：javascript复制2,3 are closest, 7,11 are most distant.
There are no adjacent primes.题目大致意思就是：告诉你一个s和e，求s和e之间靠的最近的两素数和离得最远的两素数，如果没有就输出There are no adjacent primes.这一句话。s和e范围为小于2,147,483,647的正整数，并且e和s最大相差不超过100W.
分析：首先我们不能直接去求出2到2,147,483,647的全部素数，我们不可能开21E的数组，但是我们可以求出2到sqrt（2,147,483,647）的素数表，并且根据这个来求2到2,147,483,647的全部素数。
举个例子，
我们如果知道1到10的素数：2 、3、 5、 7
那么我们可以通过这四个数，推出1到10^2的全部素数，因为1~100的所有数，如果是合数，那么至少有2、3、5、7因子之一
比如91 =13 * 7 有7
比如 81 = 9 * 9 有9
等等
那么以此类推，我们可以根据2到sqrt（2,147,483,647）的素数 来推出 2到2,147,483,647的全部素数。
当然题目输入s和e，我们只需要推出s到e的素数即可。
比如 s = 100W，e = 101W.
我们就从小素数表的2开始 把 100W 100W 2 100W 4 .。。。。。 101W-2 101W 筛掉
接着再3 从可以整除3的，并且大于等于s的第一个数开始。。。
接下去5 .。。一直到sqrt(e)为止。。。
这绝对是一个好的创举！
解题的核心思想就是这个 ，接下来贴代码：
个人原创手打，不喜勿喷
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXX = 46343;
const int BIG = 1000000 7;
bool isprime[MAXX];
int smallprime[MAXX], len1;
bool bigisprime[BIG];
int bigprime[BIG / 4], len2;
void init() {
len1 = 0;
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
for (int i = 2; i < MAXX; i ) {
if (isprime[i]) {
smallprime[len1 ] = i;
for (int j = i i; j < MAXX; j = i) {
isprime[j] = false;
}
}
}
}
void run(int s, int e) {
len2 = 0;
if (s < 2)s = 2;
memset(bigisprime, true, sizeof(bigisprime));
int k = (int)sqrt(0.0 e) 1;
for (int i = 0; i < len1 && smallprime[i] < k; i ){
int t = s / smallprime[i];
if (t * smallprime[i] < s) t ;
if (t < 2) t = 2;
for (int j = t; (long long)j * smallprime[i] <= e; j ) {
bigisprime[j * smallprime[i] - s] = false;
}
}
for (int i = 0; i <= e - s; i ) {
if (bigisprime[i]) {
bigprime[len2 ] = i s;
}
}
}
int main()
{
init();
int s, e;
while (~scanf_s("%d%d", &s, &e)) {
int maxx = -1, minn = 999, mas, mae, mis, mie;
run(s, e);
if (len2 < 2) {
puts("There are no adjacent primes.");
}
else {
for (int i = 1; i < len2 && bigprime[i] <= e; i ) {
int index = bigprime[i] - bigprime[i - 1];
if (index < minn) {
mis = bigprime[i - 1];
mie = bigprime[i];
minn = index;
}
if (index > maxx) {
mas = bigprime[i - 1];
mae = bigprime[i];
maxx = index;
}
}
printf("%d,%d are closest, %d,%d are most distant.n", mis, mie, mas, mae);
}
}
return 0;
}
