原題如下
1005. Prime Palindromes
Time Limit: 1sec Memory Limit:256MB
Description
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
簡譯：找出a到b之間既是回文數又是質數的數。
Input
There are multiple test cases.
Each case contains two integers, a and b.
a=b=0 indicates the end of input.
Output
For each test case, output the list of palindromic primes in numerical order, one per line.
Sample Input Copy
5 500
0 0 複制
Sample Output Copy
5
7
11
101
131
151
181
191
313
353
373
383 複制
思路
首先分成兩部分考慮。
回文數
怎麼找出a和b之間的回文數？一個個判斷？
有一個比較快的方法就是構造，因為根據回文數的性質，很容易構造出一定範圍内的回文數。比如，用12,可以構造出121和1221；234可以構造出23432和234432。到這裡我們大概可以看出規律了，一個n位數可以構造出2n-1或者2n位的回文數。
那從哪個數開始構造起呢？我們可以先計算下限a的位數digit，然後其(digit+1) / 2就是開始構造的數的最小位數，比如a是500，共有3位數，那麼就從2位數開始構造起，從10-99可以構造出505，606,999等比500大的回文數，如果還沒到達上限，就繼續用三位數即100-999構造，直到超出上限為止。
代碼如下：
void palindromesBetween(int a, int b){
// 根據a的位數計算下限
int digit = 0; // a 的位數
int temp = a;
while(temp > 0){
temp = temp / 10;
digit++;
}
int min = 1;
for(int i = 1; i < (digit + 1) / 2; i++){
min *= 10;
}
for(int low = min; low < b; low *= 10){ // 從最小的數開始構造
int res;
for(int i = 0; i < 2; i++){ // 分兩種情況構造
for(int num = low; num < low * 10; num++){
if(i == 0) res = num / 10; // 奇數位數
else if(i == 1) res = num; // 偶數位數
int n = num;
while(n > 0){
res = res * 10 + n % 10;
n = n / 10;
}
if(res > b) break; // 超出上限，停止構造
if(res >= a)
cout << res << endl;
}
if(res > b) break;
}
if(res > b) break;
}
} 複制
質數
一個簡單的判斷方法就是用數x除以2~x/2，如果都不能除盡，則說明x沒有除了1和本身之外的因數，則為質數。
但還有另外一個更快的方法，可以跳過很多沒必要判斷的數。原理是：一個大于等于5的質數一定可以表示為6n+1或6n+5，即除以6的餘數一定是1或5。很容易證明，因為顯然6n，6n+2，6n+3，6n+4都不是質數。
但形式為6n+1或6n+5的也不一定是質數。并且，如果x是一個質數，那麼一定有6n+1或6n+5的形式，是以必定是一個奇數，是以不可能被6n，6n+2，6n+4整除，另外如果x能被6n+3整除，那麼一定得是3的倍數，但是6n是3的倍數，是以6n+1和6n+5不可能是6n+3的倍數，即x不可能被6n+3整除。是以隻需要判斷該數能否被6n+1或6n+5整除即可，即每6個數隻需要判斷兩個數。
此外，其實并不用計算到x/2，因為一個數分解為兩個因數，一定有一個大于sqrt(x)，一個小于sqrt(x)，如果在sqrt(x)左側找不到因數，那右側肯定也找不到，是以隻需要判斷到sqrt(x)。
有了這些原理，就可以開始寫代碼了：
bool isPrime(int num){
if(num == 2 || num == 3)
return true;
if(num % 6 != 1 && num % 6 != 5){
return false;
}
for(int i = 5; i <= (int)sqrt(num); i += 6){
if(num % i == 0 || num % (i + 2) == 0){
return false;
}
}
return true;
} 複制
合并優化
有了以上的方法，合并起來就可以進行題目的求解了。但其實還可以進行優化。
因為一個偶數長度的回文數，一定可以被11整除，是以不可能是質數。
原因是11的倍數有一個性質：奇數位上數字之和 = 偶數位上數字之和，逆過來也成立。而偶數長度的回文數一定滿足這個性質，因為對稱的數位一定一個在奇數位一個在偶數位。
是以其實沒必要生成偶數位的回文數，這樣可以減少很多計算。
再結合題目的數字範圍，整合後的代碼如下：
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int);
int main(){
int a, b;
while(true){
cin >> a >> b;
if(b == 0) break;
// 先輸出a到11的質數
for(int i = a; i <= 11; i++){
if(isPrime(i)){
cout << i << endl;
}
}
// 根據a的位數計算下限
int digit = 0; // a 的位數
int temp = a;
while(temp > 0){
temp = temp / 10;
digit++;
}
int min = 10;
for(int i = 2; i < (digit + 1) / 2; i++){
min *= 10;
}
for(int low = min; low < b; low *= 10){
int res;
for(int num = low; num < low * 10; num++){
res = num / 10;
int n = num;
while(n > 0){
res = res * 10 + n % 10;
n = n / 10;
}
if(res > b) break;
if(res >= a && isPrime(res))
cout << res << endl;
}
if(res > b) break;
}
}
}
bool isPrime(int num){
if(num % 6 != 1 && num % 6 != 5){
return false;
}
for(int i = 5; i <= (int)sqrt(num); i += 6){
if(num % i == 0 || num % (i + 2) == 0){
return false;
}
}
return true;
} 複制
另外附上判斷一個數是否為回文數的方法：
思路是把這個數倒過來看是否跟原來相等。
bool isPalindrome(int num){
int newNum = 0;
int n = num;
while(n > 0){
int r = n % 10;
n = n / 10;
newNum = newNum * 10 + r;
}
return newNum == num;
} 複制