isProbPrime = True

import sys

from math import log

from random import randint

def main():

	args = parse_args()

	n = args.n

	if args.s:

		if safe_is_prime(n):

			print "%i is most probably a prime number." % n

		else:

			print "%i is not a prime number." % n

		return 

	elif args.a:

		a = args.a

	else:

		a = randint(2, n-1)

	if is_prime(n, a):

		print "%i is probably a prime." % n	

	else:

		print "%i is not a prime." % n

def safe_is_prime(n):

	aset = set()

	while len(aset) < int(log(n)):

		aset.add(randint(2, n-1))

	for a in aset:

		if not is_prime(n, a):

			return False

	return True

def is_prime(n, a=None):

	if not a:

		a = randint(2, n-1)

	global isProbPrime

	isProbPrime = True

	#print "Prime Test for %i with a = %i:" % (n, a)

	r = power(a, n-1, n)

	if r != 1 or not isProbPrime:

		#print "=> %i is not a prime." % n

		return False

	else:

		#print "=> %i is probably a prime." % n

		return True

def power(a, p, n):

	global isProbPrime	

	if p == 0:

		return 1

	x = power(a, p/2, n)

	r = (x*x)%n

	#print "power(%i, %i, %i)" % (a, p, n)

	#print "result = %i" % r

	if r == 1 and x != 1 and x != n-1:

		isProbPrime = False

		#print "isProbPrime = False"

	if p%2 == 1:

		r = (a*r)%n

		#print "updated result = %i" % r

	return r

from argparse import ArgumentParser

def parse_args():

    parser = ArgumentParser(description='Applies the randomised prime number test.')

    parser.add_argument('n', type=int, help='number to be tested')

    parser.add_argument('-a', type=int, help='provide a yourself')

    parser.add_argument('-s', action='store_true', help='multiple tests to minimise probability of failure')

    return parser.parse_args()

if __name__ == "__main__":

    main()