Solution: Building Primes Dec. 21, 2012

Here is my solution to the Programming Praxis exercise from Dec. 21, 2012. The solution is written in python.

The task:

It is sometimes possible, starting with a prime, to add a digit to the front of the number that forms a new prime. For instance, starting from prime 7, adding 1 forms prime 17, adding 3 forms prime 317, adding 6 forms prime 6317, adding 2 forms prime 26317, and so on.

Your task is to write a program to find the largest prime that can be formed in this way.

My solution:

# Author: Will Clausen
#
# Date: Jan. 13, 2013
#
# This program will solve the problem from Programming Praxis
# on Dec. 21, 2013

import math
import random

# The answer is generated in these first two functions,
# but the meat of the computation is in checking primality
def buildPrime():
	maxPrime = 1

	# Implement a depth-first search approach by generating
	# successively large primes starting from the initial
	# one-digit primes, 2, 3, 5, and 7
	for x in range(3, 10):
		if probIsPrime(x, 30):
			nextPrime = buildPrimes(x, 1)
			if nextPrime > maxPrime: maxPrime = nextPrime

	return maxPrime

# A helper function that ensures new digits are added to
# front of the old prime to check for a new prime
def buildPrimes(num, power):
	maxPrime = num

	for x in range(1, 10):
		check = num + x*pow(10, power)
		if probIsPrime(int(check), 30):
			nextPrime = buildPrimes(check, power+1)
			if nextPrime > maxPrime: maxPrime = nextPrime

	return maxPrime

def probIsPrime(num, numChecks):
	# Some optimizations
	if num == 2:
		return True

	if num % 2 == 0:
		return False

	# Here I use a list of the first 100 primes to use
	# as bases when checking primality. This will allow for
	# accurate calculations for primes of any reasonable size
	# (or even an unreasonable size, like 10^100)
	LoP = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
			31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
			73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
			127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
			179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
			233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
			283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
			353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
			419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
			467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
	i = 0

	# Unfortunately, using numbers greater than num for checking
	# causes errors, so some checking is necessary here to ensure
	# accuracy
	if (num < LoP[numChecks]):
		LoP = range(1, num)

	# The meat of the computation
	while numChecks > 0:
		check = LoP[i]
		i += 1

		# Be careful not to index out of the list of primes...
		if (i == len(LoP)):
			i = 0

		if not strongPseudoprimeTest(num, check):
			break

		numChecks -= 1

	return numChecks == 0

""" Function to check primality. It effectively employs Fermat's
	Little Theorem in a creative way to deterimine if a number,
	(the check) demonstrates the compositeness of a number (the num).
	"""
def strongPseudoprimeTest(num, check):

	# Initialize some helpful variables, nice names are unnecessary.
	d = num - 1
	s = 0
	numLessOne = num - 1

	# If d is even divide it by two and increment s
	while d % 2 == 0:
		d /= 2
		s += 1

	t = pow(check, d, num)

	if ((t == 1) or (t == numLessOne)):
		return True

	s -= 1
	while s > 0:
		s -= 1

		t = pow(t, 2, num)

		if ((t == 1) or (t == numLessOne)):
			return True

	return False

# This code produced the correct solution of 357686312646216567629137L