星空's Blog
PAT-A1015 Reversible Primes

原题

1015 Reversible Primes (20 分)

题解

做题的时候理解错了题意(英语渣哭哭惹)
这题意思是说给一个数n,判断一下n是不是素数
如果是,转换成D进制数n1,然后反转n1得到n2
将n2转换为十进制数n3,判断n3是不是素数
如果都是,输出Yes
若不能同时满足,输出No

举个栗子:

输入 23 2
n = 23(demical)(素数)
n1 = 10111(binary)
n2 = 11101(binary)
n3 = 29(demical)(素数)
输出 Yes

这题重点在进制转换,比较考验这个基本功,进制转换的时候需要反转得到的序列,本来想到用栈保存,但是题目最后要求反转回去,负负得正,所以应该是一个类似队列的操作,索性直接用string拼接一气呵成,不过这种方法在二进制到十进制的范围内是稳的,超过了十进制能不能用不好说(出错了别打我),恰好本题限定了范围 1 < D <= 10

代码

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

bool isPrime(int n) {
    //1不是素数
    //1不是素数
    //1不是素数
    if (n == 1) {
        return false;
    }
    for (int i = 2;i < n;i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

//十进制转D进制顺便反转,1 < D <= 10
int decimalToDAndReverse(int n,int d) {
    string result = ""; 
    while (n > 0) {
        result += n % d + '0';
        n = n / d;
    }
    return stoi(result,0,d);
}

int main(void) {
    int n,d;
    cin >> n;
    while (n >= 0) {
        cin >> d;
        if (isPrime(n) && isPrime(decimalToDAndReverse(n,d))) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        cin >> n;
    }
    return 0;
}
博客所有文章禁止转载。
算法AC代码仅供参考,请不要未经修改直接套用。
首页      算法学习      PAT-A1015 Reversible Primes
https://secure.gravatar.com/avatar/271861a23dcdde929d3ee8cb8c04f854?s=256&d=monsterid&r=g

星空

文章作者

发表评论

textsms
account_circle
email

星空's Blog

PAT-A1015 Reversible Primes
原题 1015 Reversible Primes (20 分) 题解 做题的时候理解错了题意(英语渣哭哭惹) 这题意思是说给一个数n,判断一下n是不是素数 如果是,转换成D进制数n1,然后反转n1得到n2 将n2转换为…
扫描二维码继续阅读
2019-08-14
分类
标签云