PAT甲级1015解法

原题链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805495863296000

思路

这题要求判断一个数在翻转前后是否都是质数。有一个难以理解的地方是在给定进制下的翻转，这是指转成该进制表示的数之后翻转，再将翻转后的数转换回十进制判断。比如11在二进制下的翻转，首先转换为二进制表示形式1011，之后翻转为1101，再转换回十进制为13判断。另外，将十进制转换为其他进制的方法是用原数不断去除以进制数，并将每次得到的余数倒序记录下来，而由于我们还需要再翻转一次，所以在计算时直接依次将余数存在vector中最终得到的就是在给定进制下翻转后的数。

代码如下

代码

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int num, radix, reverse;
	vector<int> result;	//1代表Yes，0代表No
	cin >> num;
	while (num >= 0)
	{
		reverse = 0;	//用于存储翻转后的数
		if (num < 2)	//1和0
		{
			result.push_back(0);
			cin >> num;
			continue;	//直接进入下一次循环
		}
		int flag = 1;
		cin >> radix;
		for (int i = 2; i < num; i++)	//判断原数是否为质数
		{
			if (num%i == 0)
			{
				flag = 0;
				break;
			}
		}
		vector<int> radixNum;
		while (num / radix > 0)
		{
			radixNum.push_back(num%radix);
			num /= radix;
		}
		radixNum.push_back(num);
		int exp = 1;
		for (int i = radixNum.size() - 1; i >= 0; i--)
		{
			reverse += radixNum[i] * exp;
			exp *= radix;
		}
		if (reverse < 2)	//1和0
		{
			result.push_back(0);
			cin >> num;
			continue;	//直接进入下一次循环
		}
		for (int i = 2; i < reverse; i++)	//判断翻转数是否为质数
		{
			if (reverse % i == 0)
			{
				flag = 0;
				break;
			}
		}
		result.push_back(flag);
		cin >> num;
	}
	for (int i = 0; i < result.size(); i++)
	{
		if (result[i] == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}