python - 寻找卡迈克尔数

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)，因此将错误地返回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