프로그래밍/Python
카마이클 수
daewonyoon
2021. 4. 8. 23:38
반응형
############################################
# ISBN89-7914-288-9 Programming Challenges
# problem 50 : uva 10006
# Carmichael Numbers
############################################
TRUE = 1
FALSE = 0
def pow_mod(a, b, m):
'''get the value of a**b mod m'''
ret = 1
for i in range(b) :
ret = ret*a
ret = ret%m
return ret
def IsPrime(n):
if n == 1 :
return FALSE
i = 2
while i*i <= n :
if n % i == 0 :
return FALSE
i = i + 1
return TRUE
def IsCarmichael(n):
'''nonprime n suffices :
n
i mod n = i for all i < n '''
if IsPrime(n):
return FALSE
for i in range(2, n):
if pow_mod(i, n, n) != i :
# print ("%d^%d %% %d = %d"%(i, n, n, pow_mod(i, n, n)))
return FALSE
return TRUE
#-- main --
cases= [ 1729, 17, 561, 1109, 431 ]
#cases = [ 4, 5, 6, 7, 8, 9, 10 ]
for n in cases:
if IsCarmichael(n) :
print ("The number %d is a Carmichael number."%n)
else :
print ("%d is not a Carmichael number."%n)
728x90