PAT_甲級_1015 Reversible Primes (20分) (C++)【反轉質數】

目錄

1，題目描述

題目大意

2，思路

3，代碼

1，題目描述

Sample Input:

73 10
23 2
23 10
-2
           

Sample Output:

Yes
Yes
No
           

題目大意

看了好幾遍都沒看明白。。。搜尋了大神的部落格才恍然大悟。

如果⼀個數本身是素數，⽽且在d進制下反轉後的數在⼗進制下也是素數，就輸出Yes，否 則就輸出No ；  

以23 2為例，十進制23轉換為二進制為10111，反轉後為11101，再轉換為十進制則表示29，由于23和29均為質數，故輸出Yes；

2，思路

設計兩個函數：

• bool isPrime(int num)：判斷num是否為指數；
• int convert(int num, int radix)：将num按radix進制轉換，并且反轉，最後轉換成十進制輸出；

先接受第一個數num，若為正數則接受下一字段radix，判斷num及revNum是否均為質數，是則輸出Yes，否則輸出No；

3，代碼

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;

bool isPrime(int num){
    if(num == 1) return false;
    if(num == 2) return true;
    int end = sqrt(num);                    //判斷到sqrt(num)即可
    for(int i = 2; i <= end; i++){
        if(num % i == 0) return false;
    }
    return true;
}
int convert(int num, int radix){
    vector<int> temp;
    int a = 0;
    while(num != 0){
        temp.push_back(num % radix);
        num /= radix;
    }
    for(int i = 0; i < temp.size(); i++){  //i遞增：反轉，i遞減：正常（手工模拟一下更清楚）
        a = a * radix + temp[i];           //利用 秦九韶 算法（尋找疊代公式）
    }
    return a;
}

int main(){
    int num, radix, revNum;
    scanf("%d", &num);
    while(num > 0){
        cin>>radix;
        revNum = convert(num, radix);
        (isPrime(num) == true && isPrime(revNum) == true) ? cout<<"Yes"<<endl : cout<<"No"<<endl;
        cin>>num;
    }
    return 0;
}