1.题目要求给出一个数N，该数在D进制下，数字位翻转后是否仍为质数。目前解法同时判断N和转化后的数是否同时为质数。
2.需要熟悉进制转换的方法。
3.进制转换的第一步，通过求余求出string，此时的string恰好是倒序的，直接转化为数字，判断质数即可
正确的进制转换：
[c language=”++”]
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]);
[/c]
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代码
[c language=”++”]
//#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;
}
[/c]