算法提高 特殊的質數肋骨 時間限制：1.0s 內存限制：256.0MB 提交此題 問題描述 農民約翰母?？偸钱a生最好的肋骨。你能通過農民約翰和美國農業部標記在每根肋骨上的數字認出它們。農民約翰確定他賣給買方的是真正的質數肋骨，是因為從右邊開始切下肋骨，每次還剩下的肋骨上的數字都組成一個質數。
例如有四根肋骨的數字分別是：7 3 3 1，那么全部肋骨上的數字 7331是質數；三根肋骨 733是質數；二根肋骨 73 是質數；當然,最后一根肋骨 7 也是質數。7331 被叫做長度 4 的特殊質數。
寫一個程序對給定的肋骨的數目 N (1<=N<=8),求出所有的特殊質數。數字1不被看作一個質數。 輸入格式 單獨的一行包含N。 輸出格式 按順序輸出長度為 N 的特殊質數,每行一個。 樣例輸入 4 樣例輸出 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
這個題需要點優化 如果直接打表的話 首先刪選法查找素數的復雜度就是n*sqrt(n)*2,這里的n代表范圍 10的九次方，因為是八位數 然后 - - 直接就超時了
然后這樣想 開頭必須是素數 之后的組合數也必須是素數 直接用搜索剪枝的話 - -就快了好多 秒出
#include <iostream>#include <algorithm>#include<cstdio>#include<cstring>#include <cmath>using namespace std;int su(int x){ if(x==2) return 1; if(x%2==0) return 0; for(int i=3;i*i<=x;i+=2) { if(x%i==0) return 0; } return 1;}void run(int x,int s){ if(x==0) { cout<<s<<endl; return ; } s=s*10; for(int i=1;i<=9;i++) { if(su(s+i)&&s+i!=1) { run(x-1,s+i); } }}int main(){ int n; while(cin>>n) { run(n,0); }}新聞熱點
疑難解答
