# 1015 Reversible Primes （20 分)

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?5) and D (1

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:
73 10
23 2
23 10
-2
Sample Output:
Yes
Yes
No

AC代码

`#include #include using namespace std;int isPrime(int N); //判断是否为素数int Power(int D, int M); //将D进制数转换为十进制数int Rev(int N, int D);int main() { int N, D; cin >> N; if (N < 0) return 0; //遇负数结束 cin >> D; while (true) { if (isPrime(N)) { //当输入数为素数 if (Rev(N, D)) cout << "Yes" << endl; //如果输入数D进制的倒置数仍为素数 else cout << "No" << endl; } else cout << "No" << endl; cin >> N; if (N < 0) return 0; //遇负数结束 cin >> D; } return 0;}int isPrime(int N) { int ret = 1; if (N == 1) return 0; for (int i = 2; i <= sqrt(N); i++) if (N%i == 0) { ret = 0; break; } return ret;}int Power(int D, int M) { int p = 1; for (int i = 0; i < M; i++) p *= D; return p;}int Rev(int N, int D) { int p = 0, ret = 0; int revD[10001] = { 0 }; while (N > 0) { revD[p++] = N % D; N /= D; } //实现D进制倒置数的各位存储 for (int i = p - 1; i >= 0; i--) ret += revD[i] * Power(D, p - i - 1); //得到D进制倒置数 int Judge; Judge = isPrime(ret); //判断D进制倒置数是否为素数 return Judge;}`