#-------------------------------------------------------------------------------
#  TestPrime1.py
#  Determine if a number is prime using the following fact from number theory.
#
#  Theorem: 
#  n is prime if and only if it has no prime divisor p satisfying p**2 <= n.
#
#  Equivalently:
#  n is composite if and only if it has a prime divisor p satisfying p**2 <= n.
#
#-------------------------------------------------------------------------------


# function main() -------------------------------------------------------------
def main():

   n = int(input('Enter a positive integer >1 : '))
   L = [2,3,5,11]
   for p in L:
      if n < p**2:  # p is beyond the range p**2 <= n
         print(n, 'is prime.')
         break
      # end if
      if n%p == 0:  # p divides n
         print(n, 'is composite.')
         break
      # end if
   else:  # executed only if no break was encountered
      print(n, 'may be prime or composite')
   # end for-else

# end main()

# closing conditional ---------------------------------------------------------
if __name__=='__main__':

   main()

# end