# Miller-rabin probablistic test for primality
# from http://snippets.dzone.com/posts/show/4200
# by Alexandru Scvortov; retrieved Nov 24 2008

import sys
import random

def toBinary(n):
  r = []
  while (n > 0):
    r.append(n % 2)
    n = n / 2
  return r

def test(a, n):
  """
  test(a, n) -> bool ; check whether n is not prime or not
  Returns:
    - True, if n is complex.
    - False, if n is probably prime.
  """
  b = toBinary(n - 1)
  d = 1
  for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
      return True           # not prime
    if b[i] == 1:
      d = (d * a) % n
  if d != 1:
    return True             # not prime
  return False              # probably prime

def MillerRabin(n, s = 100):
  """
    MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not

    Returns:
      - True, if n is probably prime.
      - False, if n is complex.
  """
  try:
    n = int(n)
  except:
    print "Error in MillerRabin converting '%s' to integer." % n
  if n<2: return False
  for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
      return False # n is complex
  return True # n is prime

def main(argv):
  print MillerRabin(int(argv[0]), int(argv[1]))

if __name__ == "__main__":
  main(sys.argv[1:])