当前位置: 首页 > >

1015 Reversible Primes (20 分)

发布时间:

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 (<10?5) and D (1

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
#include
using namespace std;
int isPrime(int N); //判断是否为素数
int Power(int D, int M); //将D进制数转换为十进制数
int Rev(int N, int D);
int main() {
int N, D;
cin >> N;
if (N < 0) return 0; //遇负数结束
cin >> D;
while (true) {
if (isPrime(N)) { //当输入数为素数
if (Rev(N, D)) cout << "Yes" << endl; //如果输入数D进制的倒置数仍为素数
else cout << "No" << endl;
}
else cout << "No" << endl;
cin >> N;
if (N < 0) return 0; //遇负数结束
cin >> D;
}
return 0;
}
int isPrime(int N) {
int ret = 1;
if (N == 1) return 0;
for (int i = 2; i <= sqrt(N); i++)
if (N%i == 0) { ret = 0; break; }
return ret;
}
int Power(int D, int M) {
int p = 1;
for (int i = 0; i < M; i++) p *= D;
return p;
}
int Rev(int N, int D) {
int p = 0, ret = 0;
int revD[10001] = { 0 };
while (N > 0) { revD[p++] = N % D; N /= D; } //实现D进制倒置数的各位存储
for (int i = p - 1; i >= 0; i--)
ret += revD[i] * Power(D, p - i - 1); //得到D进制倒置数
int Judge;
Judge = isPrime(ret); //判断D进制倒置数是否为素数
return Judge;
}



友情链接: