WCW

# 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.

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
```