这道题看着别人的代码写的。
1 #include <cstdio> 2 #include <cstring> 3 #define m 1000000009 4 using namespace std; 5 6 bool prime[10][10][10]; 7 int dp[10001][10][10]; 8 int temp=0; 9 10 11 void getprime() 12 { 13 memset(dp,0,sizeodp(dp)); 14 bool p[1000]; 15 memset(p,false,sizeof(p)); 16 for(int i=2; i<1000; i++) 17 { 18 if(!p[i]) 19 { 20 for(int j=i+i; j<1000; j+=i) 21 { 22 p[j]=true; 23 } 24 } 25 } 26 for(int i=100; i<1000; i++) 27 { 28 if(!p[i]) 29 { 30 int x1=i/100; 31 int x2=(i/10)%10; 32 int x3=i%10; 33 prime[x1][x2][x3]=true; 34 dp[3][x2][x3]+=1; 35 temp++; 36 } 37 } 38 } 39 int main() 40 { 41 int n; 42 scanf("%d",&n); 43 getprime(); 44 if(n==3) 45 { 46 printf("%d ",temp); 47 return 0; 48 } 49 for(int i=4; i<=n; i++) 50 { 51 for(int x1=1; x1<10; x1++) 52 { 53 for(int x2=1; x2<10; x2++) 54 { 55 for(int x3=1; x3<10; x3++) 56 { 57 if(dp[i-1][x1][x2]>0&&(prime[x1][x2][x3])) 58 { 59 dp[i][x2][x3]=(dp[i][x2][x3]+dp[i-1][x1][x2])%m; 60 } 61 } 62 } 63 } 64 } 65 int ans=0; 66 for(int x2=1; x2<10; x2++) 67 { 68 for(int x3=1; x3<10; x3++) 69 { 70 ans=(ans+dp[n][x2][x3])%m; 71 } 72 } 73 printf("%d ",ans); 74 return 0; 75 }