PAT 1015 Reversible Primes (20分) 谜一般的题目,不就是个进制转换+素数判断

题目

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

题目大意

说实在的,这个题目看到我吐血,谷歌翻译都都翻译不出来他想要的效果,我在找了好几篇博客之后看到的结论都是这个样子:

A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime.
就是说,可逆素数: 在十进制下,N是个素数,且在D进制下的数值倒过来后,再转成十进制,还是个素数

反正我是真的从这个英文中看不出来这个意思。

题目就是:给出 N, 进制 D,输出 N 是否是 可逆素数。

思路

  • 编写判断十进制数是否是素数的方法(for循环进行到它开根号就可以了)
	    for (int i = 2; i <= sqr; ++i)
        	if (n % i == 0) return false;
  • 先判断 N 是否是 素数,若不是,直接输出 No 结束。

  • 求得 ND 进制下的反转后的结果,用一个数组保存。

    比如 123 在十进制下 反转后是 321(就算只有1位或者是0也要进行一次,所以用 do while

    • n 对10取余得到3,3写进数组第一个位置;
    • n = n / 10 = 12;
    • 重复上面的步骤
  • 把反转后的数字转成十进制再判断是否是素数

	// 转成十进制
        for (int i = 0; i < len; ++i)
            n = n * radix + arr[i];

代码

只要明白题目意思,也就没有什么难度。

#include <iostream>
#include <cmath>
using namespace std;
/**
 * 这个题理解题目意思很重要
 * A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. 
 * 就是说,可逆素数: 在十进制下,N是个素数,且在D进制下的数值倒过来,再反转成十进制,还是个素数
 * 反正我是真没看出来
 */

// 是否是素数
bool isprime(int n) {
    if (n <= 1) return false;
    int sqr = sqrt(n);
    for (int i = 2; i <= sqr; ++i)
        if (n % i == 0) return false;
    return true;
}

int main() {
    // 一个十进制的n,一个给定的进制D
    int n, radix;
    while (cin >> n) {
        // 题意,最后一行只有一个负数,表示输入结束
        if (n < 0) break;
        cin >> radix;
        // 首先n在十进制下要是个素数
        if (!isprime(n)) {
            cout<< "No" << endl;
            continue;
        }
        // 得到在D进制下反转后的编码,如123在十进制下反转后是321
        int len = 0, arr[20] = {0};
        do {
            arr[len++] = n % radix;
            n = n / radix;
        }while (n > 0);
        // 转成十进制
        for (int i = 0; i < len; ++i)
            n = n * radix + arr[i];
        // 如果转换之后的数字还是素数,那么它就是 可逆素数
        cout<< (isprime(n) ? "Yes" : "No") << endl;
    }

    return 0;
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://vivi.run/archives/pat-1015-reversible-primes