写在最前面：这是一道因为各种原因被磨了很久的题，今天重新拿出来做，排bug排崩溃
题目：http://poj.org/problem?id=2689 题目大意：给定一个区间[L，R]，求出该区间内相邻两个质数中，距离最近的两个和距离最远的两个 数据范围：0<L<R<2的31次方 R-L<1000000(1e6) 样例： 输入： 2 17 14 17 输出： 2,3 are closest, 7,11 are most distant. There are no adjacent primes.
思路： 2的31次方的数据过大，无法直接用筛法筛到R为止 但是题目中特意告诉了我们R-L的范围，并且数据范围不大，也就是说我们可以先求出L到R这些数的因子，再用最朴素的算法，将L到R的合数全部进行标记 引理：任何一个合数n，都有不超过sqrt(n)的因子 所以我们只需要将数筛到sqrt(n)即可，大大缩短了时间
数组v[i]存储i的最小质因子 prime从小到大存储质数
void sha(int n) { m = 0; for (int i(2); i <= n; ++i) { if (v[i] == 0) { prime[++m] = i; v[i] = i; } for (int j(1); j <= m; ++j) { if (i*prime[j] > n || prime[j] > v[i]) break; v[i*prime[j]] = prime[j]; } } }节约空间，此时将v数组用来标记是否为合数
for (int i(1); i <= m; ++i) { if (prime[i]*prime[i] > r) break; for (int j=l/prime[i]; j <=r/prime[i]; ++j) { if ((j == 1) || (j*prime[i]-l < 0)) continue; //如果j == 1计入在内，则会把质数本身标记为合数 //j*prime[i]-l >= 0，要保证下标不过界 v[j*prime[i]-l] = 1;//L,R范围太大，为节省下标空间，把L当做0，进行标记 } }数据比较小，所以直接两层for没有太大的时间问题
long long d1,d2; long long dmax; dmax = 0; long long c1,c2; long long cmin; cmin = r-l; long long p1,p2; p1 = -1; p2 = -1; for (long long i(0); i <= (r-l); ++i) { if (!v[i]) { p1 = p2; p2 = i; if ((p2 - p1) > dmax && (p1 != -1) && (p2 != -1)) { d1 = p1; d2 = p2; dmax = p2-p1; } if ((p2 - p1) < cmin && (p1 != -1) && (p2 != -1)) { c1 = p1; c2 = p2; cmin = p2-p1; } } } if (dmax == 0) printf("There are no adjacent primes.\n"); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",c1+l,c2+l,d1+l,d2+l);完成！ 提交！ AC！ 等等 AC WA！！！！！
当我们输入13, 17时，我们发现 咦？？？为什么是-4617218172吧啦吧啦，难道没有更新么 查看cmin最初的大小以及每次更新时大小是如何比较的
cmin = r-l; if ((p2 - p1) < cmin && (p1 != -1) && (p2 != -1)) { c1 = p1; c2 = p2; cmin = p2-p1; }cmin = 17-13 =4 p2-p1 = 17-13 = 4 = cmin 没有更新过c1, c2的值，所以此时，应该把cmin的初始值再设大一点，+1即可
还有啥bug没排啊，自闭了
输入数据：1, 12345 咦？？？ １怎么算质数进去了
for (int i(1); i <= m; ++i) { if (prime[i]*prime[i] > r) break; for (int j=l/prime[i]; j <=r/prime[i]; ++j) { if ((j == 1) || (j*prime[i]-l < 0)) continue; v[j*prime[i]-l] = 1; } }仔细看朴素标记合数的代码，发现Ｌ＝１时，v[0]根本没有进循环，所以默认为初始值v[0]=0，与其他质数的状态恰好相同 那么就把这种情况单独分出来考虑 增加代码
if (l == 1) v[0] = 1;排bug的时候，一定要注意特殊的情况 像这道题，特殊情况，可能是 区间内没有质数 区间内只有一个质数 区间内的唯一质数＝Ｌ或者Ｒ Ｌ或者 R是质数？？？ Ｌ＝１的时候‘ 这些都是比较容易出错的几个点 出现WA的时候注意一下
还有这道题目 我不断出现WA的情况，并且正常的L,R的数据都是正确的情况下（那时候没有想到L＝１的情况，也没有试到有且仅有两个质数且分别等于L,R的情况） 我一度以为是我的输出问题，还看了好久，到底是空格漏了还是字母打错了，校对到怀疑人生 可能是我比较蠢
完整代码：
//poj2689 #include <cstdio> #include <cstring> #include <math.h> using namespace std; const int MAXN = 1123456; const int rsqrt = 65536; long long v[MAXN]; long long prime[rsqrt]; int m; void sha(int n); int main() { //多组数据，需要多次重复计算，所以可以直接现将所有素数筛出来 sha(rsqrt); long long l, r; while (scanf("%lld%lld", &l, &r) == 2) { memset(v, 0, sizeof(v)); for (int i(1); i <= m; ++i) { if (prime[i]*prime[i] > r) break; for (int j=l/prime[i]; j <=r/prime[i]; ++j) { if ((j == 1) || (j*prime[i]-l < 0)) continue; v[j*prime[i]-l] = 1; } } if (l == 1) v[0] = 1;// long long d1,d2; long long dmax; dmax = 0; long long c1,c2; long long cmin; cmin = r-l+1; // long long p1,p2; p1 = -1; p2 = -1; for (long long i(0); i <= (r-l); ++i) { if (!v[i]) { p1 = p2; p2 = i; if ((p2 - p1) > dmax && (p1 != -1) && (p2 != -1)) { d1 = p1; d2 = p2; dmax = p2-p1; } if ((p2 - p1) < cmin && (p1 != -1) && (p2 != -1)) { c1 = p1; c2 = p2; cmin = p2-p1; } } } if (dmax == 0) printf("There are no adjacent primes.\n"); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",c1+l,c2+l,d1+l,d2+l); } return 0; } void sha(int n) { m = 0; for (int i(2); i <= n; ++i) { if (v[i] == 0) { prime[++m] = i; v[i] = i; } for (int j(1); j <= m; ++j) { if (i*prime[j] > n || prime[j] > v[i]) break; v[i*prime[j]] = prime[j]; } } }