1.题目要求给出一个数N,该数在D进制下,数字位翻转后是否仍为质数。目前解法同时判断N和转化后的数是否同时为质数。
2.需要熟悉进制转换的方法。
3.进制转换的第一步,通过求余求出string,此时的string恰好是倒序的,直接转化为数字,判断质数即可
正确的进制转换:
while (num != 0) {//求余,把它转化为d进制格式的数,但求出来的string刚好是反的 char c = num%d + '0'; s += c; num /= d; } for (int i = 0; i < s.size() / 2; i++) swap(s[i], s[s.size() - 1 - i]);
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
AC代码
//#include<string> //#include <iomanip> #include<vector> #include <algorithm> //#include<stack> #include<set> #include<queue> #include<map> //#include<unordered_set> //#include<unordered_map> //#include <sstream> //#include "func.h" //#include <list> #include<stdio.h> #include<iostream> #include<string> #include<memory.h> #include<limits.h> using namespace std; /* 87767 */ int main(void) { vector<bool> prime(660000, true); prime[0] = false; prime[1] = false; prime[2] = true; for (int i = 2; i < 660000; i++) { if (prime[i]) { for (int j = 2; j*i < 660000; j++) { prime[j*i] = false; } } } int n, d; while (scanf("%d", &n) != EOF) { if (n < 0) return 0;//以负数结束 cin >> d; int num = n; string s = ""; while (num != 0) {//求余,把它转化为d进制格式的数,但求出来的string刚好是反的 char c = num%d + '0'; s += c; num /= d; } //for (int i = 0; i < s.size() / 2; i++) // swap(s[i], s[s.size() - 1 - i]); int reverse = 0; for (int i = 0; i < s.size(); i++) { reverse = (s[i] - '0') + reverse * d; } if (prime[n] && prime[reverse]) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }