题目

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 \le 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:

1
2
3
4

73 10
23 2
23 10
-2

Sample Output:

1
2
3

Yes
Yes
No

思路

思路很简单：

  • 求得”翻转数”。应该比较简单，具体实现见下面Rev函数
  • 判断N和N的翻转数是否都是素数

判断输入终止的方法：利用scanf的返回值。scanf的返回值为scanf已转化的 格式化标识符的个数，因此最后只有一个负数标识结束的时候，scanf会返回1，其余时候 返回2，因此用的代码中的while(scanf(...))的形式，非常简洁。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <stdio.h>

int iPrime(int N)
{
	if (N == 0 || N == 1)
		return 0;
	for (int i = 2; i * i <= N; i++)
		if (N % i == 0)
			return 0;
	return 1;
}

int Rev(int N, int D)
{
	int Nrev;
	for (Nrev = 0; N; N /= D) {
		Nrev *= D;
		Nrev += N % D;
	}
	return Nrev;
}

int main()
{
	int N, D;

	while (scanf("%d %d", &N, &D) == 2)
		puts(iPrime(N) && iPrime(Rev(N, D)) ? "Yes" : "No");

	return 0;
}