PAT (Advanced Level) Practice 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 (<) and D (1), 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 <iostream>

 #include <string.h>

 #include <cstring>

 #include <algorithm>

 #include <cstdio>

 #include <stack>

 using namespace std;

 int n,d;

 int _prime(int x)

 {

     if(x==) return ;

     int flag=;

     for(int i=;i*i<=x;i++){

         if(x%i==){

             flag=;

             break;

         }

     }

     return flag;

 }

 int _deal(int n,int d)

 {

     stack<int> s;

     while(n){

         s.push(n%d);

         n/=d;

     }

     int sum=,t=;

     while(!s.empty()){

         sum+=s.top()*t;

         t*=d;

         s.pop();

     }

     return sum;

 }

 int main()

 {

     while(cin>>n&&n>){

         cin>>d;

         int flag;

         if(!_prime(n)) flag=;

         else{

             if(_prime(_deal(n,d))) flag=;

             else flag=;

         }

         if(flag) cout<<"Yes"<<endl;

         else cout<<"No"<<endl;

     }

     return ;

 }

巴特西

PAT (Advanced Level) Practice 1015 Reversible Primes (20 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章