對於pythons來說使用米勒-拉賓法只要測試2,7兩個數字就會過了

witness=[2,7,61]
def isPrime(num):
    if num==1:
        return False
    if num==2:
        return True
    if ~num&1:
        return False
    if num==3:
        return True
    s=0
    d=num-1
    while ~d&1:
        s+=1
        d>>=1
    for i in witness:
        if i>=num:
            continue
        x=pow(i,d,num)
        if x==1 or x==num-1:
            continue
        flag=False
        for j in range(1,s):
            if pow(i,pow(2,j)*d,num)==num-1:
                flag=True
                continue
        if flag:
            continue
        return False
    return True
while True:
    o=int(input())
    if o==0:
        break
    print('質數' if isPrime(o) else '非質數')