CSP/信奧賽C++語法基礎(chǔ)刷題訓(xùn)練（23）：洛谷P1217：[USACO1.5] 回文質(zhì)數(shù) Prime Palindromes

題目描述

因為 $151$ 既是一個質(zhì)數(shù)又是一個回文數(shù)（從左到右和從右到左是看一樣的），所以 $151$ 是回文質(zhì)數(shù)。

寫一個程序來找出范圍 $[a,b](5\le a<b\le 100,000,000)$（一億）間的所有回文質(zhì)數(shù)。

輸入格式

第一行輸入兩個正整數(shù) $a$ 和 $b$。

輸出格式

輸出一個回文質(zhì)數(shù)的列表，一行一個。

樣例 #1

樣例輸入 #1

5 500

樣例輸出 #1

5
7
11
101
131
151
181
191
313
353
373
383

提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文數(shù)再判斷它們是不是質(zhì)數(shù)（素數(shù)）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要產(chǎn)生正確的回文數(shù)，你可能需要幾個像下面這樣的循環(huán)。

題目翻譯來自NOCOW。

USACO Training Section 1.5

產(chǎn)生長度為 $5$ 的回文數(shù)：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇數(shù)才會是素數(shù)for (d2 = 0; d2 <= 9; d2++) {for (d3 = 0; d3 <= 9; d3++) {palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(處理回文數(shù)...)}}}

66分代碼

#include<bits/stdc++.h>
using namespace std;
/*思路：（70分：部分測試點超時） 
函數(shù)1：判斷一個數(shù)是否是質(zhì)數(shù)
函數(shù)2：判斷一個數(shù)是否是回文數(shù) 
*/
int a,b;
//判斷一個數(shù)是否是質(zhì)數(shù)
bool isPrime(int x){if(x<=1) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true;
}
//判斷一個數(shù)是否是回文數(shù)
bool isHw(int x){int tmp=x;//記錄x的值用于過程運算 int y=0;while(tmp){y=y*10+tmp%10;tmp/=10;}if(x==y) return true;else return false;
}
int main(){cin>>a>>b;for(int i=a;i<=b;i++){if(isPrime(i) && isHw(i)){cout<<i<<endl;}}return 0;
} 

88分代碼

#include<bits/stdc++.h>
using namespace std;
/*思路：（88分：部分測試點超時） 
函數(shù)1：判斷一個數(shù)是否是質(zhì)數(shù)
函數(shù)2：判斷一個數(shù)是否是回文數(shù) 
---優(yōu)化思路：先判斷是否是回文，再判斷是否是質(zhì)數(shù)---- 
---因為質(zhì)數(shù)判斷的函數(shù)時間復(fù)雜度較高，而回文判斷的函數(shù)時間復(fù)雜度較低---- 
*/
int a,b;
//判斷一個數(shù)是否是質(zhì)數(shù)
bool isPrime(int x){if(x<=1) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true;
}
//判斷一個數(shù)是否是回文數(shù)
bool isHw(int x){int tmp=x;//記錄x的值用于過程運算 int y=0;while(tmp){y=y*10+tmp%10;tmp/=10;}if(x==y) return true;else return false;
}
int main(){cin>>a>>b;for(int i=a;i<=b;i++){if(isHw(i) && isPrime(i)){//優(yōu)化的關(guān)鍵修改在這兒 cout<<i<<endl;}}return 0;
} 

100分代碼

#include<bits/stdc++.h>
using namespace std;
/*思路：（100分）        
---新增優(yōu)化：減少b的值--- >b在10^7到10^8之間時，位數(shù)是偶數(shù)位，不可能為回文數(shù)素數(shù)>除了11以外，一個數(shù)的位數(shù)是偶數(shù)的話，不可能為回文數(shù)素數(shù)。>如果一個回文素數(shù)的位數(shù)是偶數(shù)，則它的奇數(shù)位上的數(shù)字和與偶數(shù)位上的數(shù)字和必然相等；>根據(jù)數(shù)的整除性理論，容易判斷這樣的數(shù)肯定能被11整除，所以它就不可能是素數(shù)。
*/
int a,b;
//判斷一個數(shù)是否是質(zhì)數(shù)
bool isPrime(int x){if(x<=1) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true;
}
//判斷一個數(shù)是否是回文數(shù)
bool isHw(int x){int tmp=x;//記錄x的值用于過程運算 int y=0;while(tmp){y=y*10+tmp%10;tmp/=10;}if(x==y) return true;else return false;
}
int main(){cin>>a>>b;b=min(b,9999999); //優(yōu)化b的最大值 for(int i=a;i<=b;i++){if(isHw(i) && isPrime(i)){//優(yōu)化的關(guān)鍵修改在這兒 cout<<i<<endl;}}return 0;
} 

文末彩蛋：

點擊王老師青少年編程主頁有更多精彩內(nèi)容