task<\/a>:<\/p>\nIt 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.<\/p>\n
Your task is to write a program to find the largest prime that can be formed in this way.<\/p>\n
My solution:<\/p>\n
\r\n\r\n# Author: Will Clausen\r\n#\r\n# Date: Jan. 13, 2013\r\n#\r\n# This program will solve the problem from Programming Praxis\r\n# on Dec. 21, 2013\r\n\r\nimport math\r\nimport random\r\n\r\n# The answer is generated in these first two functions,\r\n# but the meat of the computation is in checking primality\r\ndef buildPrime():\r\n\tmaxPrime = 1\r\n\r\n\t# Implement a depth-first search approach by generating\r\n\t# successively large primes starting from the initial\r\n\t# one-digit primes, 2, 3, 5, and 7\r\n\tfor x in range(3, 10):\r\n\t\tif probIsPrime(x, 30):\r\n\t\t\tnextPrime = buildPrimes(x, 1)\r\n\t\t\tif nextPrime > maxPrime: maxPrime = nextPrime\r\n\r\n\treturn maxPrime\r\n\r\n# A helper function that ensures new digits are added to\r\n# front of the old prime to check for a new prime\r\ndef buildPrimes(num, power):\r\n\tmaxPrime = num\r\n\r\n\tfor x in range(1, 10):\r\n\t\tcheck = num + x*pow(10, power)\r\n\t\tif probIsPrime(int(check), 30):\r\n\t\t\tnextPrime = buildPrimes(check, power+1)\r\n\t\t\tif nextPrime > maxPrime: maxPrime = nextPrime\r\n\r\n\treturn maxPrime\r\n\r\ndef probIsPrime(num, numChecks):\r\n\t# Some optimizations\r\n\tif num == 2:\r\n\t\treturn True\r\n\r\n\tif num % 2 == 0:\r\n\t\treturn False\r\n\r\n\t# Here I use a list of the first 100 primes to use\r\n\t# as bases when checking primality. This will allow for\r\n\t# accurate calculations for primes of any reasonable size\r\n\t# (or even an unreasonable size, like 10^100)\r\n\tLoP = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,\r\n\t\t\t31, 37, 41, 43, 47, 53, 59, 61, 67, 71,\r\n\t\t\t73, 79, 83, 89, 97, 101, 103, 107, 109, 113,\r\n\t\t\t127, 131, 137, 139, 149, 151, 157, 163, 167, 173,\r\n\t\t\t179, 181, 191, 193, 197, 199, 211, 223, 227, 229,\r\n\t\t\t233, 239, 241, 251, 257, 263, 269, 271, 277, 281,\r\n\t\t\t283, 293, 307, 311, 313, 317, 331, 337, 347, 349,\r\n\t\t\t353, 359, 367, 373, 379, 383, 389, 397, 401, 409,\r\n\t\t\t419, 421, 431, 433, 439, 443, 449, 457, 461, 463,\r\n\t\t\t467, 479, 487, 491, 499, 503, 509, 521, 523, 541]\r\n\ti = 0\r\n\r\n\t# Unfortunately, using numbers greater than num for checking\r\n\t# causes errors, so some checking is necessary here to ensure\r\n\t# accuracy\r\n\tif (num < LoP[numChecks]):\r\n\t\tLoP = range(1, num)\r\n\r\n\t# The meat of the computation\r\n\twhile numChecks > 0:\r\n\t\tcheck = LoP[i]\r\n\t\ti += 1\r\n\r\n\t\t# Be careful not to index out of the list of primes...\r\n\t\tif (i == len(LoP)):\r\n\t\t\ti = 0\r\n\r\n\t\tif not strongPseudoprimeTest(num, check):\r\n\t\t\tbreak\r\n\r\n\t\tnumChecks -= 1\r\n\r\n\treturn numChecks == 0\r\n\r\n""" Function to check primality. It effectively employs Fermat's\r\n\tLittle Theorem in a creative way to deterimine if a number,\r\n\t(the check) demonstrates the compositeness of a number (the num).\r\n\t"""\r\ndef strongPseudoprimeTest(num, check):\r\n\r\n\t# Initialize some helpful variables, nice names are unnecessary.\r\n\td = num - 1\r\n\ts = 0\r\n\tnumLessOne = num - 1\r\n\r\n\t# If d is even divide it by two and increment s\r\n\twhile d % 2 == 0:\r\n\t\td \/= 2\r\n\t\ts += 1\r\n\r\n\tt = pow(check, d, num)\r\n\r\n\tif ((t == 1) or (t == numLessOne)):\r\n\t\treturn True\r\n\r\n\ts -= 1\r\n\twhile s > 0:\r\n\t\ts -= 1\r\n\r\n\t\tt = pow(t, 2, num)\r\n\r\n\t\tif ((t == 1) or (t == numLessOne)):\r\n\t\t\treturn True\r\n\r\n\treturn False\r\n\r\n# This code produced the correct solution of 357686312646216567629137L\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"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, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[14,13,9,11,12],"class_list":["post-37","post","type-post","status-publish","format-standard","hentry","category-programming-praxis","tag-building-primes","tag-december-2012","tag-january2013","tag-programming-praxis-2","tag-solution"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=37"}],"version-history":[{"count":7,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/37\/revisions"}],"predecessor-version":[{"id":55,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/37\/revisions\/55"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=37"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=37"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}