PAT 甲级 1015 Reversible Primes（20 分） C++版

Posted on Edited on In

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进制的数转换成十进制的数。判断原先的数和反转过的数是否都是素数，即可得到结果。 根据进制转换的规则，这里省略了翻转的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

bool is_prime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int convert_new_num(int n, int d) {
    string s;
    do {
        s += to_string(n % d);
        n /= d;
    } while (n != 0);
    int result = 0, radix = 1;
    for (int i = (int) s.size() - 1; i >= 0; i--) {
        result += radix * (s[i] - '0');
        radix *= d;
    }
    return result;
}

int main() {
    int n = 0, d = 0;
    while (true) {
        scanf("%d", &n);
        if (n < 0) break;
        scanf("%d", &d);
        printf("%s\n", is_prime(n) && is_prime(convert_new_num(n, d)) ? "Yes" : "No");
    }
    return 0;
}