1015 Reversible Primes (PTA)

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 (<10​5​​) 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

编译器:Python(python3)

写了三个函数分别是:素数判断,十进制转任意进制的逆序和任意进制转十进制

import math
def IsPrime(num):
    if num == 0 | num == 1:
        return False
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

def reverse_Radix(origin_num,base_num):
    result_num_lsit = []
    if origin_num < base_num:
        return origin_num
    else:
        while True:
            div, mod = divmod(origin_num,base_num)
            # result_num_lsit.insert(0,str(mod))
            result_num_lsit.append(str(mod))
            origin_num = div
            if origin_num < base_num:
                # result_num_lsit.insert(0,str(origin_num))
                result_num_lsit.append(str(origin_num))
                result_num = int(''.join(result_num_lsit))
                return result_num

def ToDecimal(origin_num,base_num):
    result_num = 0
    index = 0
    while True:
        div, mod = divmod(origin_num,10)
        result_num = result_num + mod*base_num**index
        index+=1
        origin_num = div
        if div == 0:
            return result_num

while True:
    Input_Str = input().split(' ')
    if int(Input_Str[0]) < 0:
        break

    origin_num = int(Input_Str[0])
    base_num = int(Input_Str[1])

    reverse_num = reverse_Radix(origin_num,base_num)

    result_num = ToDecimal(reverse_num,base_num)

    if IsPrime(origin_num) & IsPrime(result_num):
        print('Yes')
    else:
        print('No')

发表评论

电子邮件地址不会被公开。 必填项已用*标注