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

时间:2022-10-04 20:30:05

题目

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;
}