PAT 1015 Reversible Primes：進制轉換與素數判斷

題目描述

給定 N (< 10^5) 和 D (1 < D ≤ 10)。判斷 N 是否為 D 進制下的可逆素數：N 是素數，且 N 的 D 進制表示反轉後對應的十進制數也是素數。

算法步驟

1. 判斷 N 是否為素數 (試除法至 √N)。
2. 將 N 轉為 D 進制：反覆取模 D 存入隊列/棧。
3. 反轉構造新數：從隊列取出數字，按 `rev = rev * D + digit` 累加。
4. 判斷反轉後的數是否為素數。
5. 輸出 Yes/No。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;

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

int main() {
    int n, d;
    while (cin >> n) {
        if (n < 0) break;
        cin >> d;
        if (!isPrime(n)) { cout << "No\n"; continue; }
        queue q;
        int tmp = n;
        while (tmp) { q.push(tmp % d); tmp /= d; }
        int rev = 0;
        while (!q.empty()) { rev = rev * d + q.front(); q.pop(); }
        cout << (isPrime(rev) ? "Yes" : "No") << endl;
    }
    return 0;
}

關鍵點

• N < 10^5，轉 D 進制後反轉數值也在 int 範圍內 (D≤10)。
• 素數判斷試除法至 √x 完全足夠 (√10^5 ≈ 316)。
• 隊列天然實現反轉：先進先出即為逆序。
• 輸入以負數結束。

示例

73 10  -> 73(10) 反轉 37 皆素數 -> Yes
23 2   -> 23(10)=10111(2) 反轉 11101(2)=29 皆素數 -> Yes
3 10   -> 3 素數 反轉 3 素數? 但樣例輸出 No... 注意：3 是素數，反轉也是 3，應為 Yes。
樣例輸出 No 可能是題目有其他隱含條件或樣例筆誤。代碼邏輯按定義正確。