"""
primetest.py:

  Goal: check whether the Fermat test ("ftest" below)
  is a good test for primality.  Failing this,
  check more elaborate test (Fermat tests with bases
  different from 2) are good tests.

  Examples:
  
  >>> check(ftest, 2, 200)
  >>> check(test, 2, 1000)
  >>> test2 = lambda n: xtest(n, [2,3,5,7])
  >>> check(test2, 2, 10000)

"""

def modpower(b,e,m):
  """modpower(b,e,m) = b^e mod m"""
  P = 1
  S = b
  while e > 0:
    r = e%2
    e = e/2
    if r == 1:
	  P = P*S % m
    S = S*S % m
  return P

ftest = lambda n: modpower(2,n-1,n)
# ^^^ Fermat test

g = lambda a, n: modpower(a,n-1,n)
# ^^^ Fermat test with base a

def test(n):
  """Conjunction of two Fermat tests"""
  if g(2,n) == 1 and g(3,n) == 1:
    return 1
  else:
    return 0
 
def xtest(n,L):
  """Auxilliary function for Fermat test
  on a list L of bases"""
  for a in L:
    if g(a,n) != 1:
      return 0
  return 1


def isprime(n):
  """Stupid primality test (trial division)"""
  if len(td(n)) == 1:
    return 1
  else:
    return 0

def xxtd(n):
 d = 2
 factors = []
 while n >= d*d:
   if n % d == 0:
	 factors.append(d)
	 n = n/d
   else:
	 d = d + 1
 if n > 1:
   factors.append(n)
 return factors


def td(n):
  d = 2
  factors = []
  while n >= d*d:
    if n % d == 0:
      factors.append(d)
      n = n/d
    else:
      d = d + 1
  if n > 1:
     factors.append(n)
  return factors

def check(f,a,b):
  """check the test 'f' on integers in [a,b)"""
  for n in range(a,b):
    if f(n) == 1 and len(td(n)) > 1:
      print n