1. # include<stdio.h>
2. # include<stdlib.h>
3. # include<string.h>
4. # include<math.h>
5. unsigned long data[2000] ;
6. int count;
7. char str[20];
8. char str1[20];
9. char str2[20];
10.
11. int cmp(const void *a,const void *b)
12. {
13. return *(unsigned long *)a-*(unsigned long *)b;
14. }
15.
16. int issushu(unsigned long num)
17. {
18.
19. unsigned long i,j ,k = num;
20.
21. for (j = (unsigned long)sqrt(k),i = 2;i <= j+1;i++)
22. if (num%i==0)
23. return 0;
24.
25. return 1;
26.
27. }
28. void _itoah(int n,int digit )
29. {
30. int i = 0;
31. for(i = 0;i < digit;i ++)
32. {
33. //str[digit-i-1] = n%10 + '0';
34. str[digit-i-1] = n%10 + '0';
35. n /=10;
36. }
37.
38. }
39. void _itoad(int n,int digit,int b )// 針對 奇數和偶數的不同 增加一個標志位
40. {
41. int i = 0,j = digit;
42. if(b==1)
43. digit ++;
44. for(i = 0;i < j;i ++)
45. {
46. str[digit++] = n%10 + '0';
47. n /=10;
48. }
49. }
50. void even_huiwen(int n)
51. {
52. long i ,j,digit = n/2,tmp = 0;
53. //j = (long)pow(10,digit) -1;
54. j = (long)pow(10,digit) -1;
55. for(i = (long)pow(10,digit-1); i <= j;i++ ) //i代表偶數的高位//(long)pow(10,n-1); i <= j;i++ )
56. {
57.
58. _itoah(i,digit);
59. _itoad(i,digit,0);
60. str[n] = '\0';
61. strcpy(str1,str);
62. strrev(str1);
63. if (!strcmp(str1,str)) if(issushu(atol(str)))
64. data[count ++] = atol(str);//printf("%ld\t",atol(str)),data[count ++] = atol(str);
65.
66. memset(str,NULL,sizeof(str));
67. memset(str1,NULL,sizeof(str1));
68.
69. }
70. }
71. void odd_huiwen(int n)
72. {
73. long i ,j,k,digit = n/2,tmp = 0;
74. j = (long)pow(10,digit) -1;
75.
76. for(k = 0;k < 10; k ++) // 奇數位中間的數字
77. for (i = (long)pow(10,digit-1);i <= j ; i ++)
78. {
79. _itoah(i,digit);
80. str[digit] = k + '0';
81. _itoad(i,digit,1);
82. str[n] = '\0';
83. strcpy(str1,str);
84. strrev(str1);
85. if (!strcmp(str1,str)) if(issushu(atol(str)))
86. data[count ++] = atol(str);//printf("%ld\t",atol(str)),data[count ++] = atol(str);
87.
88. memset(str,NULL,sizeof(str));
89. memset(str1,NULL,sizeof(str1));
90. }
91. }
92. int main()
93. {
94. unsigned long a,i,j,x,y;
95. data[0] = 2,data[1] = 3,data[2] = 5,data[3] = 7,data[4] = 11;
96. //freopen("pprime1.out","w",stdout);
97. count = 5;
98. int n;
99.
100. //生產所有的回文素數
101. for(int _digit = 3; _digit <= 8;_digit+=2)
102. {
103. if(_digit%2==0)
104. even_huiwen(_digit);
105. else
106. odd_huiwen(_digit);
107. }
108.
109. qsort(data,count,sizeof(unsigned long ),cmp);
110. scanf("%d",&n);
111. while (n--)
112. {
113. scanf("%ld%ld",&x,&y);
114. for (i=0;data[i] <=y&&i<=count;i++)
115. {
116. if (data[i]>=x)
117. printf("%ld\n",data[i]);
118. }
119.
120. }
121.
122. return 0;
123.
124. }
posted on 2010-03-04 09:23
付翔 閱讀(518)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構