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 (<) and D (1), you are supposed to tell if N is a reversible prime with radix D.
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.
For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.
73 10
23 2
23 10
-2Yes
Yes
No首先判断N,若N不是素数直接输出No，否则将其转换为D进制，然后逆序，再将逆序后的D进制数转换为十进制数q，判断q是否为素数即可。
#include <bits/stdc++.h> using namespace std; bool isPrime(int n) {//判断素数 if (n <= 1) return false; for (int i = 2; i <= sqrt(n); ++i) { // i*i<=n也可 if (n % i == 0) return false; } return true; } vector<int> changeD(int num, int d) {//将N转换为D进制数 vector<int> result; do { result.push_back(num % d); num /= d; } while (num != 0); return result; } int BtoA(vector<int> num, int d) {//将逆序之后的D进制数转换为十进制数q int p = 1, result = 0; for (int i = num.size() - 1; i >= 0; --i) { result += p * num[i]; p *= d; } return result; } int n, d; int main() { while (1) { cin >> n; if (n < 0) break; cin >> d; if (!isPrime(n)) {//N不是素数直接跳过 cout << "No\n"; continue; } vector<int> nums = changeD(n, d); int n = BtoA(nums, d); if (isPrime(n)) { cout << "Yes\n"; } else { cout << "No\n"; } } return 0; }
package main import ( "fmt" ) func isPrime(n int) bool { if n <= 1 { return false } for i := 2; i*i <= n; i++ { if n%i == 0 { return false } } return true } func changeD(n, d int) []int { var result []int for { result = append(result, n%d) n /= d if n == 0 { break } } return result } func bToA(nums []int, d int) int { result, p := 0, 1 for i := len(nums) - 1; i >= 0; i-- { result += nums[i] * p p *= d } return result } func main() { var n, d int for { fmt.Scan(&n) if n < 0 { break } fmt.Scan(&d) if !isPrime(n) { fmt.Println("No") continue } num := changeD(n, d) n = bToA(num, d) if isPrime(n) { fmt.Println("Yes") } else { fmt.Println("No") } } }
原文：https://www.cnblogs.com/tao10203/p/13771397.html