# PAT-A 真题- 1015. Reversible Primes

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 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

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

bool isPrime(int num){
if(num < 2 ) return false;
if(num == 2) return true;
for(int i = 2; i < num / 2; i++)
if(num % i == 0) return false;
return true;
}

int convert(int num, int d){
int arr[32] = {0};
//使用除基取余法转d进制
int len = 0;
do{
arr[len++] = num % d;
num /= d;
}while(num != 0);
//反转的同时转10进制
for(int i = len - 1; i >= 0; i--)
num += (arr[i] * pow(d, len - 1 - i));
return num;
}

int main(){
while(1){
int num, d;
cin >> num;
if(num < 0) break;
cin >> d;
if(isPrime(num) && isPrime(convert(num, d)))
cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}