PAT甲级真题1015 可逆质数
给定两个整数 N 和 D，如果 N 是一个质数，并且将 N 转化为 D 进制表示后，再进行反转，得到的新数字转化为十进制表示后如果也是一个质数，则称 N 在 D 进制系统中，是一个可逆质数。
例如，N=73,D=10，则 73 是质数，其十进制表示反转后为 37 也是质数，所以 73 在十进制系统中是一个可逆质数。
N=23,D=2，则 23 是质数，其二进制表示为 10111，反转后得到 11101，转化为十进制后为 29，这也是一个质数，所以 23 在二进制系统中是一个可逆质数。
现在，请你判断所给 N 在 D 进制系统中是否是一个可逆质数。
输入格式
输入包含多组测试数据。
每组数据共一行，包含两个整数 N 和 D。
当输入一行为一个负数时，表示输入停止。
输出格式
对于每组数据，输出一个结果，占一行。
如果所给 N 在 D 进制系统中是一个可逆质数，则输出 Yes，否则输出 No。
数据范围
1≤N<10^5,
1<D≤10
输入样例：
73 10 23 2 23 10 -2
输出样例：
Yes Yes No
解题思路
此题主要要思考这么几个问题：
- 怎么判断一个数是质数 推荐文章《判断质数》
- 怎么转化为10进制 ：秦九韶算法
- 怎么转化为 d 进制
答案都在酒(代码)里了
AC代码
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; typedef long long LL; //判断质数 bool isPrime(LL num) { if (num <= 3) { return num > 1; } // 不在6的倍数两侧的一定不是质数 if (num % 6 != 1 && num % 6 != 5) { return false; } LL sqrtc = (LL)sqrt(num); for (LL i = 5; i <= sqrtc; i += 6) { if (num % i == 0 || num % (i + 2) == 0) { return false; } } return true; } //转化为10进制 LL getn(char c) { if(c<='9')return c-'0'; else return c-'a'+10; } LL cal_10(string n,LL d){ LL ret=0; for(auto c : n){ ret = ret*d + getn(c); } return ret; } //转化为d进制 string transd(string n,LL d){ string ch;//余数 LL cur = stoll(n); string ans=""; while(cur!=0){ ch = to_string(cur%d); ans = ans + ch; cur = cur / d; } return ans; //置反D进制的结果:从上往下看的时候就是它转化结果的字符的置反 } int main() { string n; LL d; while(cin>>n>>d){ //如果本身不是质数直接输出No if(!isPrime(stoll(n))){ cout<<"No"<<endl; }else{ //转化为D进制 string dnum = transd(n,d); //再转换为10进制 LL tenNum = cal_10(dnum,d); //判断是否为质数 if(isPrime(tenNum))cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
