P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
题意 找出所有 n 位的十进制数要求其每一个前缀均为质数
搜索
加两个剪枝 ， 1、最高位有4种选择 ，可以选择 2 3 5 7
然后其他位只有 5 种选择 选 1 3 5 7 9
2、高位向低位枚举 这样 枚举的时候如果当前这个数已经不满足质数肋骨
那就直接 跳出，这是一个小优化 即一边做一边判断 是否为质数 这样就能剪掉很多
1 #include <cstdio> 2 #include <cmath> 3 #include <string> 4 #include <cstdlib> 5 #include <iomanip> 6 #include <iostream> 7 #include <algorithm> 8 #include <string> 9 using namespace std ; 10 11 int n ; 12 int a[6] ; 13 14 bool is_prime(int x) // 是质数 返回 true 15 { 16 if(x<=1) return false ; 17 for(int i=2;i*i<=x;i++) 18 if(x%i==0) return false ; 19 return true ; 20 } 21 22 void dfs(int k,int sum ) 23 { 24 int x ; 25 for(int i=1;i<=5;i++) 26 { 27 x = sum*10+a[i] ; 28 if(is_prime(x)) 29 { 30 if(k==n) printf("%d ",x) ; 31 else dfs(k+1,x) ; 32 } 33 34 } 35 36 } 37 38 int main() 39 { 40 scanf("%d",&n) ; 41 a[ 1 ] = 1 ; 42 a[ 2 ] = 3 ; 43 a[ 3 ] = 5 ; 44 a[ 4 ] = 7 ; 45 a[ 5 ] = 9 ; 46 int x ; 47 for(int i = 1;i<=4;i++) 48 { 49 x = a[ i ] ; 50 if(i==1) x = 2 ; 51 dfs(2,x) ; 52 } 53 54 return 0 ; 55 }