判断原数和在指定进制下逆序后转为的10进制数是否都是素数

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

实现思想

将原数进行素数的判断

将原数进行进制转换然后逆序处理

将逆序数转为10进制数进行素数判断

若两个判断条件都为true则输出Yes否则输出No

代码实现

#include <cstdio>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>

using namespace std;

string intToA(int n,int radix)
{
    string ans="";
    do{
        int t=n%radix;
        if(t>=0&&t<=9)    ans+=t+'0';
        else ans+=t-10+'a';
        n/=radix;
    }while(n!=0);
    reverse(ans.begin(),ans.end());
    return ans;
}

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

int str2Dec(string s, int r) {
    int sum = 0;
    int index = 0;
    for(int i  = s.length() - 1; i >= 0; i--){
        sum += (s[i] - '0') * pow(r, index++);
    }
    return sum;
}

int main() {
    int n, r;
    string str;

    scanf("%d", &n);
    while(n > 0){
        bool flag = true;
        scanf("%d", &r);
        str = intToA(n, r);
        reverse(str.begin(), str.end());
        int s = str2Dec(str, r);
        if(isPrime(n) == true && isPrime(s) == true) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
        scanf("%d", &n);
    }


    return 0;
}