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 结束。

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

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wppzyy.html