找到卡迈克尔数

Question

我似乎不明白为什么我的python代码告诉我错误的carmichael数字。提前谢谢。我只是看不出算法中的错误。在

def isCarmichaelNumber( x ):
    for y in range(2,x):
        #check if prime
        if math.gcd (x, y) == 1:
            if pow(y, x-1, x) != 1:
                return False
    return True

print(isCarmichaelNumber(1847))

Answer 1

您没有检查x是否为素数。根据定义，卡迈克尔数必须是复合数。对于任何素数x，pow(y, x-1, x) == 1对于range(2, x)中的所有y，因此将错误地返回True。1847是素数，这就是为什么你的函数声称它是一个卡迈克尔数。在

一种解决方法：

def isCarmichaelNumber(x):
    import math
    isprime = True
    for y in range(2,x):
        if math.gcd(x, y) == 1:
            if pow(y, x-1, x) != 1:
                return False
        else:
            isprime = False
    return not isprime