Codechef May 2013 WitMath

I thought that by referencing the editorial and following faithfully I could have the solution out in minutes. Turned out to be hours..totally forgot how to do repeated squaring. Good revision, this was.

	# My first attempt at implementing Miller-Rabin primality test
	# decided to implement it instead of stealing from somewhere
	# in order to understand it
	# v2. fixed the miller rabin pass function. Now correct.
	# v3. a**s is too slow for large numbers
	# v4. using def apowbmodn(a,b,n):
	# if b==1: return a
	# return apowbmodn(a*a,b/2,n) if b%2==0 else apowbmodn(a,b-1,n)*a
	# is too slow! My guess is that the stack isn't that huge to accomodate such
	# computation.
	# v5. redesigned my modular exponential function.
	# I studied the solution from
	# http://www.codechef.com/viewsolution/2167990
	# got an Non Zero Exit Code error =\
	# v6. getting an OverflowError in the statement for i in xrange(N-1)
	# fixed; no longer using xrange
	import random
	import sys
	def miller_rabin_pass(a,r,n):
	a = a % n
	if a == 1: return True
	for z in xrange(r-1):
	if a == n-1: return True
	a = (a*a) % n
	return a == n-1
	def apowbmodn(a,b,n):
	binary = ""
	while b > 0:
	if b & 1 == 0:
	binary += "0"
	else:
	binary += "1"
	b >>= 1
	result = 1
	for i in xrange(len(binary)):
	result = (result * result)%n
	if binary[len(binary)-i-1] == "1":
	result = (result * a)%n
	return result
	def isProbablyPrime(n):
	if n == 2: return True
	if n % 2 == 0: return False
	random.seed()
	if n < 100:
	for i in xrange(2,n): # lazy to put sqrt
	if n%i ==0: return False
	return True
	else:
	s = n-1
	r = 0
	while s % 2 == 0:
	r += 1
	s /= 2
	for z in xrange(30):
	a = int(random.random() *(n-1))+1
	if not miller_rabin_pass(apowbmodn(a,s,n),r,n):
	return False
	return True
	T = int(sys.stdin.readline().strip())
	for z in xrange(T):
	N = int(sys.stdin.readline().strip())
	while 1:
	if isProbablyPrime(N):
	print N
	break
	N -= 1

view raw gistfile1.txt hosted with ❤ by GitHub