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

73 10
23 2
23 10
-2
           

Sample Output:

Yes
Yes
No
           

題目大意：

• 可逆素數判斷：一個十進制數 N 在 D進制 下反轉後的十進制數仍為素數，則為可逆素數
• 注意前後均為十進制，隻是在D進制下反轉

代碼：

#include <iostream>

using namespace std;
bool isPrime(int n){
    if(n <= )
        return false;
    for(int i=; i*i<=n; i++){
        if(n%i == )
            return false;
    }
    return true;
}
int main()
{
    bool flag = true;
    int n, d;
    while(flag){
        cin >> n;
        if(n < )
            break;
        cin >> d;//進制
        if(isPrime(n) == false){
            cout << "No" << endl;
            continue;
        }
        int revers = ;//D進制下反轉後的數
        while(n != ){//D進制下反轉
            int temp = n%d;
            revers = revers*d + temp;
            n /= d;
        }
        if(isPrime(revers) == false){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }
    return ;
}