2020.2.9更新，修改打表程序，用上freopen(“Table.txt”, “w”, stdout);程序更加簡潔

---

題目描述

因為151既是一個質數又是一個回文數(從左到右和從右到左是看一樣的)，所以 151 是回文質數。
寫一個程序來找出范圍[a,b](5 <= a < b <= 100,000,000)( 一億)間的所有回文質數;

輸入輸出格式

輸入格式

第 1 行: 二個整數 a 和 b .

輸出格式：

輸出一個回文質數的列表，一行一個。

輸入輸出樣例

輸入樣例

5 500

輸出樣例

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

---

分析

• 看到這道題的第一個想法就是用循環遍歷 a 到 b 之間的奇數，然后判斷那個數是不是回文質數，是則輸出，否則訪問下一個，算法時間復雜度O(n^2)。但是數的范圍是5~1,000,000,000(一億)，如果輸入a=5，b=1,000,000,000， 即使把偶數篩選掉，再把除11外的位數為偶數的數去掉，在O(n^2)的時間復雜度下也一樣會超時。

tip： 一般情況下，我們認為OJ評測機1秒能處理10^8條指令。
O(N2)下，N最大能取8000左右
O(N3)下的話，N最大能取500左右
O(N LOG N）一般500000左右 排序能2000000

• 在以上方法行不通的情況下，我們選擇可以選擇打表。一般打表有兩種思想：

• 第一種，直接在程序中用比較優化的算法，建立一個包含題目所給的范圍內的所有回文質數的數組，然后再對建立的數組進行訪問即可。
• 第二種，先在一個程序中用相對比較暴力的方法（當然，越優化越好）求出所有的回文質數，然后輸出到.txt文件中。最后把.txt 文件中的數據復制到另個程序的數組中（直接給數組賦一大波初值）。表即成！

• 根據第一點分析可知，第一種思想會導致時間超限，故我們采用第二種思想。

---

代碼如下

暴力打表部分

#include <iostream> #include <cstdio> #include <cmath> #include <cstdio> using namespace std; const int N=1e7; const int maxn=1e7; int a[maxn]={2,3}; bool check(int x)//用于檢測x是否為回文數 {int newed=0,n=x;do{newed=newed*10+n%10;n/=10;}while(n>0);if(x==newed)//判斷反位數是否等于本身return true;elsereturn false; } int main() {//將結果輸出到同一目錄下的Table.txt文件中freopen("Table.txt", "w", stdout);int i,j,ans=0,cnt=2;for(i=5;i<=N;i+=2){for(j=1;a[j]<=sqrt(i)&&j<cnt;j++)if(i%a[j]==0)break;if(a[j]>sqrt(i)){a[cnt++]=i;if(check(i)){printf("%d,",i);//把符合條件的數輸出到.txt文件中//%d后面加個','是為了下個程序開數組時的方便ans++;}}}cout<<cnt<<endl;cout<<ans<<endl;//為了方便等下開數組，這里需要知道有多少個回文質數return 0; }

提交部分

#include <iostream> using namespace std; const int maxn=1000; int table[maxn]={5,7,11,101,131,151,181,...,9981899,9989899}; //table[maxn]是用于存儲txt文本中數據的數組 //由于數據過多，就沒有全部展示 int main() {int a,b,i;cin>>a>>b;for(i=0;i<=781;i++){if(table[i]>b)break;if(table[i]>=a&&table[i]<=b)//把在a，b之間的回文質數輸出cout<<table[i]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的P1217 回文质数（打表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。