PAT(Advanced) 1015 Reversible Primes C++实现
PAT(Advanced) 1015 Reversible Primes C++实现
题目链接
1015 Reversible Primes
题目大意
可逆素数指的是一个数若在任意数制中是素数，则在该数制中逆转的该数也是素数
算法思路
对于给定的一个数，在十进制下，判断该数是否为素数，若不为素数则必然不是可逆素数，若为素数，则通过除基取余法求得d进制“逆数”的序列，将进制序列转为十进制，最后判断是否素数
AC代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Fri Oct 09 09:43:46 2020
*/
#include<bits/stdc++.h>
using namespace std;bool prime(int x) {if (x == 1) {return false;}for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) {return false;}}return true;
}int convert(int n, int d) {// 栈存储数的d进制序列，出栈序列即为数的d进制逆序列stack<int> s;while (n > 0) {s.push(n % d);n /= d;}int value = 0;int weight = 1;while (!s.empty()) {value += s.top() * weight;weight *= d;s.pop();}return value;
}int main(int argc, char const *argv[]) {int n, d;while (~scanf("%d", &n) && n > 0) {scanf("%d", &d);printf("%s\n", prime(n) ? (prime(convert(n, d)) ? "Yes" : "No") : "No");}return 0;
}鸣谢
PAT
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
PAT(Advanced) 1015 Reversible Primes C++实现
PAT(Advanced) 1015 Reversible Primes C++实现
题目链接
1015 Reversible Primes
题目大意
可逆素数指的是一个数若在任意数制中是素数，则在该数制中逆转的该数也是素数
算法思路
对于给定的一个数，在十进制下，判断该数是否为素数，若不为素数则必然不是可逆素数，若为素数，则通过除基取余法求得d进制“逆数”的序列，将进制序列转为十进制，最后判断是否素数
AC代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Fri Oct 09 09:43:46 2020
*/
#include<bits/stdc++.h>
using namespace std;bool prime(int x) {if (x == 1) {return false;}for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) {return false;}}return true;
}int convert(int n, int d) {// 栈存储数的d进制序列，出栈序列即为数的d进制逆序列stack<int> s;while (n > 0) {s.push(n % d);n /= d;}int value = 0;int weight = 1;while (!s.empty()) {value += s.top() * weight;weight *= d;s.pop();}return value;
}int main(int argc, char const *argv[]) {int n, d;while (~scanf("%d", &n) && n > 0) {scanf("%d", &d);printf("%s\n", prime(n) ? (prime(convert(n, d)) ? "Yes" : "No") : "No");}return 0;
}鸣谢
PAT
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
发布评论