1015.Reversible Primes

2017-12-01

英文描述

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

中文描述

反转素数
在任何数字系统中一个可以反转的素数是指这个数字在那个系统中通过“反转”也是一个素数。举个例子，一个十进制系统中的一个数字73是一个可以反转的素数，因为他的反转数字37也是一个素数。现在有任意两个正整数N（< 105）和D（1 < D <= 10），你要求得这个这个正数N是否是D进制的反转数。
输入规格：
一个输入文件包含一些测试用例。每个测试用例在一行内包含两个整数N和D，当输入的N为负数时，一位这个测试文件结束了。
输出规格：
对于每个测试用例，如果N是一个在D进制中可以反转的素数就输出“Yes”否则就输出“No”
样例输入:
73 10
23 2
23 10
-2
样例输出:
Yes
Yes
No

分析与解题

1 输入的数字是一些十进制整数，也就是说不一定是素数，故先判断是否为素数
2 如果是素数，之后翻转这个数字，之后计算翻转后的数字是不是也是素数
3 翻转。题目给出的N是十进制数字，故先要把十进制数字转换为D进制数字。通过十进制变化为D进制数字的方法为：除D取余法（此处不再详细讨论）。得到的结果是一个翻转后的D进制数。再通过D进制数转换为十进制数的方法，D进制的各个位数乘上D的位置次方后再相加。D进制转换为10进制，从高位开始或者从低位开始都可以，但要需要记住D进制数字的位数。
4 最后判断翻转后的十进制数字是否为素数。
ps：输出格式，之前都是将所有的输出存放在数组中，通过判断数值的标志值来输出，这次看了ZJU上的代码，发现可以判断一个输出一个。在人工调试的时候，这样的输出是伴随着输入一个就输出一个进行执行的，起初以为这样是违规的，这次试验后，发现也是可以通过的，所以之后可以看情况来采用这样的方法来进行输出。关于分析与代码的构造，看了ZJU的代码，发现代码的构造条理清晰明了，这点值得学习。期间有一个点没有通过，后来调试后，发现是结构问题，并不是解决主要问题的方法，比如判断是否为素数以及十进制转D进制出了问题，是在输入格式上出现了错误，自己看了ZJU的代码后，有意识的朝着它的代码去更改，最后虽然与ZJU的代码不同，但是我发觉那个没过去的点已经通过了，所以我想问题是出在了输入结构那边。

C语言实现

#include<stdio.h>
#include<math.h>
int y[64] = {0};
int isprime(int p)
{
	if(p == 0 || p == 1)
		return 0;
	int i = 2;
	while(i < p)
	{
		if((p % i) == 0)
			return 0;
		i++;
	}
	return 1;
}
int main()
{
	int n, d;
	while(1)
	{
		scanf("%d", &n);
		if(n < 0)
			break;
		else
			scanf("%d", &d);
		if(isprime(n) == 1)
		{
			//反转
			int j = 0;
			while(n != 0)
			{
				y[j] = n % d;
				n /= d;
				j++;
			}
			//将反转数字转换为十进制数字
			int k = 0;
			int sum = 0;
			j--;
			while(j >= 0)
			{
				sum += y[k] * (int)(pow(d, j));
				j--;
				k++;
			}

			//判断是否为素数
			if(isprime(sum) == 1)
				puts("Yes");
			else
				puts("No");
		}
		else
			puts("No");
	}
	return 0;
}

测试链接

click me