PAT (Advanced Level) Practice 1015 Reversible Primes (20 分) 凌宸1642

题目描述：

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⁵) and D (1< D ≤ 10) , you are supposed to tell if N is a reversible prime with radix D.

译：一个可逆素数是：在某个数制中是一个素数，它在该数制中的“逆”也是一个素数。例如，在十进制中，73是可逆素数，因为它的逆37也是素数。现在给你任意两个正整数 N ( <10⁵) 和 D (1< D ≤ 10) ，你应该说明 N是否是 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.

译：每个输入文件包含几个测试用例，每个用例包含两个正整数 N 和D占一行。以输入一个负数作为结束标志。

Output Specification (输出说明):

For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.

译：对于每个测试用例，在一行中输出，如果 N 是 D 数制下的可逆素数输出 Yes 否则输出 No。

Sample Input (样例输入):

Sample Output (样例输出):

Yes

Yes

No

The Idea：

设计到素数，首先想到了先将题目范围内的所有素数标记出来，利用筛法将所有素数对应的下标位置的数据值为 false。对于每个测试用例，在输入 N 后，判断 N 是否是一个素数，若不是素数可以直接输出 No ，如果 N 是一个素数，再将 N 转为 D 数制下的数字并取逆，再将其表示的数算 x出来，再判断 x 是否是一个素数，如果x是一个素数，则输出Yes，否则输出 No 。

The Codes:

#include<bits/stdc++.h>

using namespace std ;

#define MAX 100010

bool prime[MAX] = { false } ; // 初始化

void isPrime(){	// 筛选法求素数

	for(int i = 2 ; i < MAX ; i ++ )

		if(!prime[i])

			for(int j = i + i ; j < MAX ; j += i)

				prime[j] = true ;	// i是素数，则 i 的所有倍数都不可能是素数

	prime[1] = true ;	// 注意 1 不是素数

}

int reverseNofD(int n , int d){

	int m = 1 , eve[105] , cnt = 0 ;

	for( ; n != 0 ; n /= d)  eve[cnt ++] = n % d ;

	for(int i = cnt - 1 ; i >= 0 ; m *= d , i --) // 逆置求加权值

		n += m * eve[i];

	return n ;

}

int main(){

	isPrime() ; // 先标记素数

	int n , d ;

	while(scanf("%d" , &n) , n >= 0){

		scanf("%d" , &d) ;

		if(!prime[n]) // n 是素数

			if(!prime[reverseNofD(n , d)]) printf("Yes\n") ; // 且 D 数制也是一个素数

			else printf("No\n") ;

		else printf("No\n") ;

	}

	return 0;

}

巴特西

PAT (Advanced Level) Practice 1015 Reversible Primes (20 分) 凌宸1642