카마이클 수

############################################
# 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)