sprime解題報告?—— icedream61 博客園（轉(zhuǎn)載請注明出處）
------------------------------------------------------------------------------------------------------------------------------------------------
【題目】
　　列出所有N位的超級素數(shù)。
　　所謂超級素數(shù)，即指其任意位前綴均為素數(shù)。例如7、73、733、7331均為素數(shù)，故而7331為超級素數(shù)。
【數(shù)據(jù)范圍】
　　1<=N<=8
【輸入樣例】
　　4
【輸出樣例】
　　2333
　　2339
　　2393
　　2399
　　2939
　　3119
　　3137
　　3733
　　3739
　　3793
　　3797
　　5939
　　7193
　　7331
　　7333
　　7393
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　逐位枚舉+篩法+試除法。
　　這道題需要逐位枚舉，具體過程描述如下：
　　　　1.定義0位的素數(shù)只有0（為了編程方便），調(diào)用函數(shù)go(0,0);
　　　　2.函數(shù)go(k,x)主體：x是k位的超級素數(shù)，枚舉y=x*10+i(i=0~9)，由篩法所得數(shù)組判斷，若y為超級素數(shù)則調(diào)用go(k+1,y);
　　　　3.函數(shù)go(k,x)邊界：當(dāng)k==N時，輸出x并return;
　　　　4.函數(shù)go(k,x)特判（置于邊界判斷后）：當(dāng)k==7&&N==8時，枚舉y=x*10+i(i=0~9)，由試除法判斷，若y為超級素數(shù)則調(diào)用go(k+1,y);
　　值得一提的是，這里的特判可以大大提高運行效率，大約從2s縮減到0.2s，性價比很高。
------------------------------------------------------------------------------------------------------------------------------------------------
【總結(jié)】
　　又是同樣的問題，好奇怪！為什么100,000,000過不了？求解答啊！
　　我的處理方法是：令max=10,000,000，對于N==8的情況，在枚舉到第8位的時候采用試除法判素數(shù)。這樣便可以過了。
　　不過這樣的處理倒是很不錯的，因為這樣一來篩法的時間變成了十分之一，而到8位可枚舉的數(shù)已經(jīng)少之又少，所以程序的運行效率提高極為顯著。原來代碼運行時間是2s+，現(xiàn)在只有不到0.2s了。學(xué)習(xí)了！

------------------------------------------------------------------------------------------------------------------------------------------------

【代碼】

1 /* 2 ID: icedrea1 3 PROB: sprime 4 LANG: C++ 5 */ 6 7 #include <iostream> 8 #include <fstream> 9 #include <cmath> 10 using namespace std; 11 12 const int maxd = 10000000; 13 bool d[1+maxd]; 14 15 int N; 16 17 bool isPrime(int x) 18 { 19 for(int i=2;i<=sqrt(x);++i) 20 if(x%i==0) return false; 21 return true; 22 } 23 24 void go(int k,int x,ofstream &out) 25 { 26 if(k==N) { out<<x<<endl; return; } 27 x*=10; 28 if(N==8 && k==7) 29 { 30 for(int i=0;i<=9;++i) 31 if(isPrime(x+i)) go(k+1,x+i,out); 32 return; 33 } 34 for(int i=0;i<=9;++i) 35 if(!d[x+i]) go(k+1,x+i,out); 36 } 37 38 int main() 39 { 40 ifstream in("sprime.in"); 41 ofstream out("sprime.out"); 42 43 d[0]=d[1]=true; 44 for(int i=1;i<=10000;++i) 45 if(!d[i]) 46 for(int j=i+i;j<=maxd;j+=i) d[j]=true; 47 48 in>>N; 49 50 go(0,0,out); 51 52 in.close(); 53 out.close(); 54 return 0; 55 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/icedream61/p/4324523.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的USACO Section1.5 Superprime Rib 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。