Sample Input
1. 2 17 2. 14 17
Sample Output
1. 2,3 are closest, 7,11 are most distant. 2. 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)为止。。。
这绝对是一个好的创举！
解题的核心思想就是这个 ，接下来贴代码：
个人原创手打，不喜勿喷
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. #include<cmath> 5. using namespace std; 6. const int MAXX = 46343; 7. const int BIG = 1000000 + 7; 8. bool isprime[MAXX]; 9. int smallprime[MAXX], len1; 10. bool bigisprime[BIG]; 11. int bigprime[BIG / 4], len2; 12. void init() { 13. len1 = 0; 14. memset(isprime, true, sizeof(isprime)); 15. isprime[1] = false; 16. for (int i = 2; i < MAXX; i++) { 17. if (isprime[i]) { 18. smallprime[len1++] = i; 19. for (int j = i + i; j < MAXX; j += i) { 20. isprime[j] = false; 21. } 22. } 23. } 24. } 25. void run(int s, int e) { 26. len2 = 0; 27. if (s < 2)s = 2; 28. memset(bigisprime, true, sizeof(bigisprime)); 29. int k = (int)sqrt(0.0 + e) + 1; 30. for (int i = 0; i < len1 && smallprime[i] < k; i++){ 31. int t = s / smallprime[i]; 32. if (t * smallprime[i] < s) t++; 33. if (t < 2) t = 2; 34. for (int j = t; (long long)j * smallprime[i] <= e; j++) { 35. bigisprime[j * smallprime[i] - s] = false; 36. } 37. } 38. for (int i = 0; i <= e - s; i++) { 39. if (bigisprime[i]) { 40. bigprime[len2++] = i + s; 41. } 42. } 43. } 44. int main() 45. { 46. init(); 47. int s, e; 48. while (~scanf_s("%d%d", &s, &e)) { 49. int maxx = -1, minn = 999, mas, mae, mis, mie; 50. run(s, e); 51. if (len2 < 2) { 52. puts("There are no adjacent primes."); 53. } 54. else { 55. 56. for (int i = 1; i < len2 && bigprime[i] <= e; i++) { 57. int index = bigprime[i] - bigprime[i - 1]; 58. if (index < minn) { 59. mis = bigprime[i - 1]; 60. mie = bigprime[i]; 61. minn = index; 62. } 63. if (index > maxx) { 64. mas = bigprime[i - 1]; 65. mae = bigprime[i]; 66. maxx = index; 67. } 68. } 69. printf("%d,%d are closest, %d,%d are most distant.\n", mis, mie, mas, mae); 70. } 71. } 72. return 0; 73. }
