PAT 1015 Reversible Primes (20分)

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 (<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

给定条件:
1.一个十进制数n
2.一个整数d ,1<d<=10

要求:
1.判断n是否为素数
2.判断n转换成d进制后,将数字变为“倒序”(如十进制1234倒过来为4321二进制1101倒过来为1011)然后再转换为10进制,是否为素数
3.如果两个都为素数,输出Yes否则输出No


import math
a=[]
while(1):
    tmp=input()
    if(tmp[0]=='-'):
        break
    a.append(list(map(int,tmp.split())))
def DecToNow(dec,now):  #取余法
    res=''
    while(dec!=0):
        remain=dec%now
        # if(remain>9):
        #     remain=chr(remain-9+65)
        res=str(remain)+res
        dec=int(dec/now)
    return res
def NowToDec(num,now):  #定义法
    res=0
    length=len(num)
    k=1
    for i in range(length-1,-1,-1):
        tmp=num[i]
        # if(tmp>='A'):
        #     tmp=10+ord(tmp)-65
        res+=int(tmp)*k
        k*=now
    return res

def isPrimes(num):
    if (num <= 1):
        return 0
    for i in range(2,int(math.sqrt(num))+1):   #记得+1
        if (num % i == 0):
            return 0;
    return 1;

for item in a:
    new=DecToNow(item[0],item[1])
    new_reverse=new[::-1]
    dec_reverse=NowToDec(new_reverse,item[1])
    if(isPrimes(dec_reverse) and isPrimes(item[0])):
        print("Yes")
    else:
        print("No")
        

发表评论

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