1015. Reversible Primes.md

【PAT A-1015】Reversible Primes

题意概述

判断数字 N 以及 N 在进制 D 下的翻转数是否均为素数。例如 73 在进制 10 下的翻转数为 37。

输入输出格式

输入的每一行给出两个正整数 N 和 D，最后一行以一个负数结束。

针对输入的每一行，如果数字 N 以及 N 在进制 D 下的翻转数均为素数，输出Yes，否则输出No。

数据规模

$$0<N\le {10}^5,\ 0<D \le 10$$

算法设计

解决本题需要将进制转换和判断素数的方法结合起来。需要留意的是，我们可以进制转换和翻转这一操作糅合在一起，具体实现可以参考下面的代码。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
bool isPrime(gg n) {
    if (n < 2)
        return false;
    for (gg i = 2; i <= (gg)sqrt(n); ++i)
        if (n % i == 0)
            return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, di;
    while (cin >> ni and ni >= 0) {
        cin >> di;
        gg k = 0, m = ni;
        while (m != 0) {
            k = k * di + m % di;
            m /= di;
        }
        cout << (isPrime(ni) and isPrime(k) ? "Yes\n" : "No\n");
    }
    return 0;
}