[PAT解题报告] Reversible Primes
给定自然数n，不超过105，再给定d, 问n是否是质数,并且把n化成d进制后，把数字倒过来（123变成321）还是不是质数。
注意1不是质数。
分析： 不难。主要有两个考点：
（1） 把n化成d进制，再翻转数字。 这个我们不断地除以d就好了，而且先得到的是低位数字，我们直接用x = x * d + n %
d，最终x就是翻转后的结果了，很方便， O(logn)
（2）
判断x是否是质数，一个数的最小的约数不超过sqrt(x)，所以循环没有必要到x，但从本题的数据范围似乎循环到x也没大问题，不过还是推荐sqrt(x)吧,
O(sqrt(x)) = O(x0.5)
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
bool prime(int x) {
if (x <= 1) {
return false;
}
for (int i = 2; x / i >= i; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
int main() {
for (;;) {
int n;
scanf("%d",&n);
if (n < 0) {
break;
}
int d;
scanf("%d",&d);
if (prime(n)) {;
int x = 0;
for (; n; n /= d) {
x = x * d + n % d;
}
puts(prime(x)?"Yes":"No");
}
else {
puts("No");
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1015
中移(苏州)软件技术有限公司工作强度 29人发布