PAT 甲級 1015 Reversible Primes

1015 Reversible Primes （20 point(s)）

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:

73 10
23 2
23 10
-2      

Sample Output:

Yes
Yes
No      

Experiential Summing-up

This question must be clearly read. The definition of reversible prime is a number which is prime and the decimal form of the reverse of the number's corresponding number in specified radix is also a prime.Certainly annoyed.However, only understanding this will you pass all test points.

#include <cstdio>
const int maxn=100010;
bool flag[maxn]={false};
void find_prime()
{
  flag[0]=flag[1]=true;
  for(int i=2;i<maxn;++i)
  {
    if(flag[i]==false)
    {
      for(int j=i+i;j<maxn;j+=i)
      {
        flag[j]=true;
      }
    }
  }
}
int convert(int x,int d)
{
  int product=1,ans=0,z[40],len=0;
  do
  {
    z[len++]=x%d;
    x/=d;
  }while(x);
  for(int i=len-1;i>=0;--i)
  {
    ans+=z[i]*product;
    product*=d;
  }
  return ans;
}
int main()
{
  int n,d;
  find_prime();
  while(~scanf("%d",&n))
  {
    if(n<0)
      break;
    scanf("%d",&d);
    int res=convert(n,d);
    printf("%s\n",flag[res]==false&&flag[n]==false?"Yes":"No");
  }
  return 0;
}