A1015 Reversible Primes (20 point(s))

D进制的回文判断

1. 原文

原题

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<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

2. 解析

判断n是否为素数，将数字转换成d进制的数，反转后判断是否为素数

3. AC代码

#include<cstdio>
#include<cmath>
bool isPrime(int x){
	if(x<2){
		return false;
	}
	int sqr = sqrt(1.0*x);
	for(int i = 2;i<=sqr;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	int n,d;
	while(true){
		scanf("%d%d",&n,&d);
		if (n<0)
		{
			break;
		}
		int temp = 0;
		bool flag = isPrime(n);
		do{
			temp = temp*d+n%d;
			n/=d;
		}while(n!=0);
		if (flag&&isPrime(temp))
		{
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
}