PAT 1015

时间：2014-02-21 12:46:56 收藏：0 阅读：397

1015. Reversible Primes (20)

A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (< 10⁵) and D (1 < D <= 10), you are supposed to tell if N is a reversible prime with radix D.

Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

Output Specification:

For each test case, print in one line "Yes" if N is a reversible prime with radix D, or "No" if not.

Sample Input:

Sample Output:

Yes 
Yes 
No

采用素数筛选法，若$i$为素数，则$i*j$不是素数，其中$j=2,3,....$。另外在判断$i$是否为素数时只需要循环到$\sqrt{i}$即可。

代码

1 #include <stdio.h>
2 #include <math.h>
3
4 char primerTable[500000];
5
6 void calculatePrimerTable();
7 int isPrimer(int);
8 int num2array(int,int,int*);
9 int array2num(int*,int,int);
10 int main()
11 {
12     calculatePrimerTable();
13     int N,D,len;
14     int data[32];
15     while(scanf("%d",&N)){
16         if(N < 0)
17             break;
18         scanf("%d",&D);
19         if(primerTable[N] == ‘N‘){
20             printf("No\n");
21             continue;
22         }
23         len = num2array(N,D,data);
24         if(primerTable[array2num(data,len,D)] == ‘Y‘)
25             printf("Yes\n");
26         else
27             printf("No\n");
28     }
29     return 0;
30 }
31
32 void calculatePrimerTable()
33 {
34     int i;
35     for(i=2;i<500000;i++){
36         if(primerTable[i] != ‘N‘){
37             if(isPrimer(i)){
38                 primerTable[i] = ‘Y‘;
39                 int j,n;
40                 for(j=2,n=2*i;n<500000;++j,n=j*i){
41                     primerTable[n] = ‘N‘;
42                 }
43             }
44         }
45     }
46 }
47
48 int isPrimer(int x)
49 {
50     int i,n;
51     n = (int)floor(sqrt((double)x));
52     int flag = 1;
53     for(i=2;i<=n;++i){
54         if(x % i == 0){
55             flag = 0;
56             break;
57         }
58     }
59     return flag;
60 }
61
62 int num2array(int n,int base,int *s)
63 {
64     if(n < 0)
65         return 0;
66     else if(n == 0){
67         s[0] = 0;
68         return 1;
69     }
70     int len = 0;
71     while(n){
72         s[len++] = n % base;
73         n = n / base;
74     }
75     return len;
76 }
77
78 int array2num(int *s,int len,int base)
79 {
80     int i,n = 0;
81     for(i=0;i<len;++i){
82         n = n * base + s[i];
83     }
84     return n;
85 }

原文：http://www.cnblogs.com/boostable/p/pat_1015.html