C++編程練習-回文素數

Description
一個數如果從左往右讀和從右往左讀數字是相同的，則稱這個數是回文數，如121，1221，15651都是回文數。給定位數n，找出所有既是回文數又是素數的n位十進制數。（注：不考慮超過整型數范圍的情況）。
Input
位數n,其中1<=n<=9。
Output
第一行輸出滿足條件的素數個數。
第二行按照從小到大的順序輸出所有滿足條件的素數，兩個數之間用一個空格區分。
Sample Input
1
Sample Output
4
2 3 5 7
參考代碼

1. #include <cstdio>
2. #include <cmath>
3. #include <cstdlib>
4. #include <string>
5. using namespace std;
6. int result[5960];
7. int r_s = 0;
8. int digit[10];
9. int a,b;
10. int pm[10000];
11. int pm_size = 0;
12. void init();
13. class MyString:public string{
14. public:
15. MyString(int n);
16. bool isPlalindrome();
17. private:
18. string ds;
19. };
20. MyString::MyString(int n){
21. while(n){
22. char ch = (n % 10) + '0';
23. n /= 10;
24. ds.push_back(ch);
25. }
26. }
27. bool MyString::isPlalindrome(){
28. int len = ds.length();
29. int mid = len / 2;
30. for(int i = 0;i < mid; ++ i){
31. if(ds[i] != ds[len - i - 1]){
32. return false;
33. }
34. }
35. return true;
36. }
37. void work( int c )
38. {
39. int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;
40. if ( c == 1 )
41. {
42. if ( a <= 2 && b >= 2 )
43. result[r_s ++] = 2;
44. if ( a <= 3 && b >= 3 )
45. result[r_s ++] = 3;
46. if ( a <= 5 && b >= 5 )
47. result[r_s ++] = 5;
48. if ( a <= 7 && b >= 7 )
49. result[r_s ++] = 7;
50. digit[c] = 4;
51. return ;
52. }
53. for ( i = 0; i < p; i++ )
54. s *= 10;
55. for ( i = 1; i < 10; i += 2 )
56. {
57. for ( j = 0; j < s; j++ )
58. {
59. r = i * s + j;
60. t1 = j / 10;
61. t2 = p - 1;
62. while ( t2 )
63. {
64. r = r * 10 + ( t1 % 10 );
65. t1 /= 10;
66. t2--;
67. }
68. r = r * 10 + i;
69. if ( r < a )
70. continue;
71. if ( r > b ){
72. return ;
73. }
74. MyString s(r);
75. if(s.isPlalindrome()){
76. bool bl = true;
77. for(int p = 0;p < pm_size && pm[p] < r;++ p){
78. if(r % pm[p] == 0){
79. bl = false;
80. break;
81. }
82. }
83. if(bl){
84. result[r_s ++] = r;
85. digit[c] ++;
86. }
87. }
88. }
89. }
90. }
92. int main( )
93. {
94. int i, p, c;
95. a = 2; b = 1000000000;
96. p = 1;
97. c = 0;
98. init();
99. while ( p < a )
100. {
101. c++;
102. p *= 10;
103. }
104. p /= 10;
105. while ( p < b )
106. {
107. if ( c == 2 )
108. {
109. digit[c] = 1;
110. result[r_s ++] = 11;
111. }
112. if ( c & 1 )
113. work( c );
114. c++;
115. p *= 10;
116. }
117. int n,start,end;
118. scanf("%d",&n);
119. printf("%d\n",digit[n]);
120. start = (int)pow(10.0,n-1);
121. end = (int)pow(10.0,n);
122. for(i = 0;i < r_s;++ i){
123. if(result[i] >= start && result[i] <= end){
124. printf("%d ",result[i]);
125. }
126. }
127. printf("\n");
128. return 0;
129. }
130. void init(){
131. for(int p = 2;p <= 100000;++ p){
132. bool bl = true;
133. for(int k = 2;k <= sqrt(1.0 * p);++ k){
134. if(p % k == 0){
135. bl = false;
136. break;
137. }
138. }
139. if(bl){
140. pm[pm_size ++] = p;
141. }
142. }
143. for(int i = 0;i < 10;++ i){
144. digit[i] = 0;
145. }
146. }