xiaoou33对既是素数又是回文的数特别感兴趣。比如说151既是素数又是个回文。现在xiaoou333想要你帮助他找出某个范围内的素数回文数，请你写个程序找出 a 跟b 之间满足条件的数(5 <= a < b <= 100,000,000)。 Input: 这里有许多组数据，每组包括两组数据a跟b。 Output: 对每一组数据,按从小到大输出a，b之间所有满足条件的素数回文数（包括a跟b）每组数据之后空一行。 Sample Input: 5 500 Sample Output: 5 7 11 101 131 151 181 191 313 353 373 383
解题思路：先进行素数打表，打好之后查找例题中所给的两个值的最近素数，（像我这种小白，只能先用算法找到一个最近的元素，之后再通过外调二分查找函数来找出刚刚找到的那个邻近值的索引）找到索引之后遍历判断就可以了，需要先把数字转换成字符串（之所以是_atoi_s是因为在VS评判时他认为老版本不安全），然后调用判断回文的函数判断输出就好了。 代码如下：
#include #include #include #include using namespace std;
#define MAXN 100000 #define MAXL 1000000 int prime[MAXN]; bool check[MAXL];
int Binarysearch(int s[], int x, int low, int high) { while (low <= high) { int middle = (high + low) / 2; if (x < s[middle])high = middle - 1; else if (x > s[middle])low = middle + 1; else return middle; } return high + 1; } bool isplain(char* s) { string str(s); char m[100]; strcpy_s(m, str.c_str()); char* front = m; char* back = m + strlen(m) - 1; while (front < back) { if (*front == *back) { front++; back–; } else return false; } return true; }
int main() { int n = 10000, count;
memset(check, 0, sizeof(check)); count = 0; for (int i = 2; i <= n; i++) { if (!check[i]) //如果是素数 prime[count++] = i; //记录在数组中 for (int j = 0; j < count; j++) { if (i * prime[j] > MAXL) //判断是否越界 break; // 过大的时候跳出 check[i * prime[j]] = 1; //如果check[i*prime[j]]是已知素数的整数倍那一定是合数 if ((i % prime[j]) == 0) // 如果i是一个合数，而且i % prime[j] == 0 break; } } int a, b; while (cin >> a >> b) { int* it1 = lower_bound(prime, prime + count, a); int* it2 = lower_bound(prime, prime + count, b); int i1 = Binarysearch(prime, a, 0, count - 1); int i2 = Binarysearch(prime, b, 0, count - 1); char c[100]; for (int i = i1; i <= i2; i++) { _itoa_s(prime[i], c, 10); if (isplain(c)) cout << prime[i] << endl; } } return 0;}
