描述 现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。 如果输入的整数本身就是素数，则输出该素数本身，距离输出0 输入 第一行给出测试数据组数N(0 < N <= 10000) 接下来的N行每行有一个整数M(0 < M < 1000000)， 输出 每行输出两个整数 A B. 其中A表示离相应测试数据最近的素数，B表示其间的距离。 样例输入 3 6 8 10 样例输出 5 1 7 1 11 1
下面代码解决了上述问题的功能，但是时间却超时了，在想想其他的方法优化代码：
#include <iostream> #include <cmath> #include <stdio.h> using namespace std; typedef struct a { int pro; int dec; }Node; int main() { Node node[10000]; int node_i[10000]; int flag = 0; int k; int n; int m; scanf("%d",&n); for(int i = 0 ; i < n ; i++) { scanf("%d",&node_i[i]); if(m == 1) { node[i].pro = 2; node[i].dec = 1; continue; } k = node_i[i] + 1; while(k--) { for(int j = 2 ; j < k ; j++) { if( k % j == 0) { flag = 1; break; } } if(flag == 0) { node[i].pro = k; node[i].dec = node_i[i] - k; break; } flag = 0; } k = node_i[i]; while(k) { for(int j = 2 ; j < k ; j++) { if( k % j == 0) { flag = 1; break; } } if(flag == 0) { if(node[i].dec > (k - node_i[i])) { node[i].pro = k; node[i].dec = k - node_i[i]; } break; } flag = 0;k++; } } for(int i = 0 ; i < n ; i++) { printf("%d %d\n",node[i].pro,node[i].dec); } return 0; }算法思路： 将输入的数字先找前面第 i 位，在对应找后面第 i 位，如果找到前面的返回，如果找到后面的返回。 这样大大缩小了查找素数的个数引起的不必要循环。
优化代码1（用函数调用是代码简单而且容易看懂，代码1优化把原来的O(N^2)转换成O(1)）：
#include <iostream> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; typedef struct a { int pro; int dec; }Node; bool is_prime(int num) { if(num == 1) return false; for(int i = 2 ; i <= sqrt(num) ;i++) if(num % i == 0) return false; return true; } int main() { Node node[10000]; int k,n,m,i,j = 1; int flag = 1; scanf("%d",&n); for(i = 0 ;i < n ; i++) { scanf("%d",&m); k = m; while(!is_prime(k)) { if(k == 1) flag = 0; k = m; if(flag){k = k - j ;flag = 0;} else{k = k + j;flag = 1;j++;} }//代码最大优化部分 node[i].pro = k; node[i].dec = abs(k - m); j = 1;flag = 1; } for(int i = 0 ; i < n ; i++) { printf("%d %d\n",node[i].pro,node[i].dec); } return 0; }优化代码2：
#include<iostream> #include<cmath> using namespace std; bool isprime(int n) { for(int k = 2;k <= sqrt((double)n); k++) if((n % k) == 0) return false; return true; }//这个比上述代码优化好多 int main() { int n; cin>>n; while(n--) { int num,i,j; cin >> num; if(num == 1) { cout<<"2 1"<<endl; continue; } for(i = num; !isprime(i); i--); for(j = num; !isprime(j); j++);//这俩个循环比上面巧妙一点。 if((num - i) <= (j - num)) cout << i << ' ' << (num - i) << endl; else if((num - i) > (j - num)) cout << j << ' ' << (j - num) << endl; } }