1015. Reversible Primes (20)

#include <iostream>
#include <cmath>
using namespace std;

/*
 要求：（1）判断该数是否为素数（2）判断该数基于d进制的逆序的十进制数是否为素数
 思路：（1）IsPrime判断素数  （2）基于d进制的逆序，并转换为十进制
 */

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 main(int argc, const char * argv[]) {
    int n, d;
    while (scanf("%d", &n) != EOF) {
        if (n < 0) {
            break;
        }
        scanf("%d", &d);
        if (!IsPrime(n)) {
            printf("No\n");
            continue;
        }
        
        //基于d进制的逆序(给出的数是十进制呀 所以要换成d进制后再逆序)
        int a[100], m = 0, len = 0;
        while (n) {
            a[len++] = n % d;
            n /= d;
        }
        for (int i = 0; i < len; i++) {
            m = m * d + a[i];
        }
        
        if (IsPrime(m)) {
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    
    return 0;
}