原题目

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 (< 10⁵) and D (1< D ≤10), you are supposed to tell if N is a reversible prime with radix D.

Input Specication:

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

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

题目大意

给出一个整数和它的进制，判断该整数及该整数在该进制下的反转数是否为素数。
例如，23在2进制下的表示为10111，其反转11101的十进制值29也为素数。故需输出Yes。

题解

简单题，理解题意即可。求素数的方法直接选择最朴素的遍历。

C语言代码如下：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>

int is_prime(int n){
    if(n == 0 || n == 1){
        return 0;
    }
    for(int i = 2;i <= sqrt(n);++i){
        if(n % i == 0)
            return 0;
    }
    return 1;
}

char* num_to_string(int d, int radix){
    char *ret = malloc(20);
    int i = 0;
    while(d){
        ret[i] = d % radix + '0';
        d /= radix;
        i++;
    }
    ret[i] = '\0';
    return ret;
}

int convert_reverse(char *num, int radix){
    int ret = 0;
    int base = 1;
    int i = strlen(num) - 1;
    while(num[i] == '0') i--;
    for(i;i >= 0;--i){
        ret += base * (num[i] - '0');
        base *= radix;
    }
    return ret;
}

int main(){
    int d;
    while(scanf("%d", &d)){
        if(d < 0)
            break;
        int radix;
        scanf("%d", &radix);
        if(is_prime(convert_reverse(num_to_string(d, radix), radix)) && is_prime(d))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}