(PAT 1015) Reversible Primes (进制转换+判断素数)

r囧r小猫 2022-04-23 04:20 159阅读 0赞

A **reversible prime** in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (<105) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.

### Input Specification: ###

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

### Output Specification: ###

For each test case, print in one line `Yes` if N is a reversible prime with radix D, or `No` if not.

### Sample Input: ###

73 10
    23 2
    23 10
    -2

### Sample Output: ###

Yes
    Yes
    No

解题思路:

将给出的10进制数给出后转为对应的进制数,然后判断这个数以及这个数的对称是不是素数

进制转换法为取余法:

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <math.h>
    using namespace std;
    
    bool isPrime(int num) {
    	if (num <= 1) return false;
    	for (int i = 2; i*i <= num; ++i) {
    		if (num%i == 0) return false;
    	}
    	return true;
    }
    int BTOD(string num, int Rad) {
    	int res = 0;
    	for (int i = 0; i < num.length(); ++i) {
    		res += (num[i] - '0') * pow(Rad, i);
    	}
    	return res;
    }
    void DToB(int num,int Rad) {
    	int index = 0;
    	string input;
    	int temp = num;
    	while (temp) {
    		input += to_string(temp % Rad);
    		temp = temp / Rad;
    	}
    	
    	string newstring;
    	for (int i = input.length()-1; i >= 0; --i) {
    		newstring += input[i];
    	}
    	if (isPrime(BTOD(input,Rad)) && isPrime(BTOD(newstring,Rad))) {
    		cout << "Yes" << endl;
    	}
    	else {
    		cout << "No" << endl;
    	}
    }
    int main() {
    	
    	int TNum , Dnum;
    	scanf("%d", &TNum);
    	while (TNum > 0) {
    		scanf("%d", &Dnum);
    		DToB(TNum, Dnum);
    		scanf("%d", &TNum);
    	}
    	system("PAUSE");
    	return 0;
    }