# This program contains functions that check for primality, as well as
# functions for computing the next prime.

# global array that contains list of known primes
Primes = [2,3,5,7,11,13,17,19,23]

# Procedure for checking if a number is prime, using Primes as much as
# possible.  The "Prime Factorization Theorem" states that every number is
# the product of primes.  For example, 15 = 3*5, 9 = 3*3.  Thus if a number
# is not evenly divisible by a prime number, then it is not evenly divisible
# by any number.

# In the following procedure to check if a number is prime, we first
# check if the number is in the list of known primes using binary search
# because the list of known primes is sorted (in increasing order).

def binsearch(x,A):  # returns True iff x in A, A must be sorted
    start,end = 0,len(A)  # valid indices are between start and end-1
    ax = False  # answer accumulator
    while start<end and not(ax):
        mid = (start+end)/2
        if A[mid] == x: ax = True
        if A[mid]<x: start = mid+1
        if A[mid]>x: end = mid
    return ax
#binsearch


def prime(n):  # boolean function to test if n is prime
  # if-elses needed to take care of special cases
  if n<2: return False  # return immediately exits the function 
  if binsearch(n,Primes): return True  # already known to be prime
  p = 0   # used to index Primes array
  case = Primes[p] # test case to divide against
  limit = n**0.5   # calculate square root of n, largest test case possible
  answer = True  # will be changed to false if not prime
  while answer==True and case <= limit:
     if n%case==0: answer = False
     p = p+1  # next prime to test against, if it exists
     if (p<len(Primes)):
         case = Primes[p] # load next prime
     else:
         case = case+2    # test against next odd number (assuming p>0)
  # while
  return answer
#prime(n)

print prime(57)
print prime(59)


## function to extend the Primes array:

# this function take no argument, and returns nothing, but appends 
# global array
def addNextPrime():  
    candidate = Primes[len(Primes)-1]+2  # largest known prime+2
    while not(prime(candidate)):
        candidate = candidate+2
    # while
    Primes.append(candidate)
# addNextPrime

n = 100
while n>0:
  addNextPrime()
  n -= 1
# add 100 new primes

print Primes