pat 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 (<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:

Sample Output:

Yes

Yes

No

 #include <map>

 #include <set>

 #include <queue>

 #include <cmath>

 #include <stack>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstring>

 #include <climits>

 #include <iostream>

 #include <algorithm>

 #define wzf ((1 + sqrt(5.0)) / 2.0)

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = 1e4 + ;

 int n, r;

 bool is_prime(int n)

 {

     if (n ==  || n == ) return false;

     for (int i = ; i * i <= n; ++ i)

         if (n % i == ) return false;

     return true;

 }

 int main()

 {

     while (scanf("%d", &n), n >= )

     {

         scanf("%d", &r);

         if (!is_prime(n))

         {

             printf("No\n");

             continue;

         }

         int cnt = , ans = ;

         stack <int> my_stack;

         while (n)

         {

             my_stack.push(n % r);

             n /= r;

         }

         while (my_stack.size())

         {

             ans += my_stack.top() * (pow(r, cnt));

             ++ cnt;

             my_stack.pop();

         }

         if (!is_prime(ans))

             printf("No\n");

         else

             printf("Yes\n");

     }

     return ;

 }

巴特西