题目
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 (<105) 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
N
N is a reversible prime with radix
D
D
D, or No if not.
Sample Input:
73 10
23 2
23 10
-2
Sample Output:
Yes
Yes
No
题目大意
给出一个数N和一个表示进制的数D，如果该数和在对应进制下反转后的数字都是素数，则输出Yes，否则No
思路
首先可以通过欧拉筛法来建立一个素数判断表；对于给定的数和表示进制的数，获得其在对应进制数下的表示，可以存放在字符串中，得到反转后的数并判断是否是素数。
代码中字符串s获得的时候已经是反转的情况
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxN
= 1000010;
int ifsu
[maxN
]={0};
void initial(){
for(int i
=2; i
<maxN
; i
++){
if(!ifsu
[i
]){
for(int j
=i
+i
; j
<maxN
; j
+=i
){
ifsu
[j
] = 1;
}
}
}
}
int getNum(int a
, int radix
){
string s
= "";
while(a
!= 0){
s
+= (a
% radix
+ '0');
a
= a
/radix
;
}
int sum
= 0, p
=0;
for(int i
=s
.size()-1; i
>=0; i
--){
sum
+= pow(radix
, p
++) * (s
[i
]-'0');
}
return sum
;
}
int main(int argc
, const char * argv
[]) {
int a
, radix
;
ifsu
[1] = 1;
initial();
while(true){
scanf("%d", &a
);
if(a
< 0) break;
scanf("%d", &radix
);
if(!ifsu
[a
]){
int sum
= getNum(a
, radix
);
if(!ifsu
[sum
]) printf("Yes\n");
else printf("No\n");
}else
printf("No\n");
}
return 0;
}
