반응형
############################################
# 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
'프로그래밍 > Python' 카테고리의 다른 글
[Python|초보] 난수행렬 만들기 (0) | 2021.06.01 |
---|---|
[Python] TypeError: unsupported operand type(s) for (0) | 2021.05.03 |
파이썬 xlrd.biffh.XLRDError: Excel xlsx file; not supported (0) | 2021.03.14 |
Connected Component (0) | 2021.02.23 |
파이썬초보 : 숫자계단 (0) | 2021.02.04 |