The Problem:<\/p>\n
What is the 10 001st prime number?<\/p>\n
My Solution (in Python):<\/p>\n
\r\n\r\n# Author: Will Clausen\r\n#\r\n# Date: Jan 7, 2013\r\n#\r\n# This program will solve Problem 7 from Project Euler\r\n\r\nimport math\r\nimport time\r\n\r\n# This function solves problem 7 from Project Euler.\r\n# This function uses a primality tester implemented with\r\n# trial division. This solution is the second fastest.\r\n# See the other implementations below.\r\ndef problem7(limit):\r\n\tprimesSeen = 1\r\n\tcheck = 3\r\n\r\n\twhile primesSeen < limit:\r\n\t\tif isPrime(check, 30):\r\n\t\t\tprimesSeen += 1\r\n\t\t\tlastPrime = check\r\n\r\n\t\tcheck += 2\r\n\r\n\treturn lastPrime\r\n\r\n# This function solves also solves problem 7, but\r\n# uses the Miller-Rabin primality test to check\r\n# if a number is prime instead of trial division.\r\n# This solution is not as fast as either of the\r\n# other solutions.\r\ndef problem7_2(limit):\r\n\tprimesSeen = 1\r\n\tcheck = 3\r\n\r\n\twhile primesSeen < limit:\r\n\t\tif probIsPrime(check, 30):\r\n\t\t\tprimesSeen += 1\r\n\t\t\tlastPrime = check\r\n\r\n\t\tcheck += 2\r\n\r\n\treturn lastPrime\r\n\r\n# This solution to problem 7 uses the Prime Number Theorem\r\n# (hidden in a couple helper functions below) and the sieve\r\n# of Eratosthenes to quickly solve the problem. This is the\r\n# fastest solution.\r\ndef problem7_3(limit):\r\n\r\n\tLoP = firstPrimes(limit)\r\n\r\n\treturn LoP[-1]\r\n\r\n\r\n# Helper function to generate primes less than an integer\r\n# input. The sieve of Eratosthenes is the method used to\r\n# generate the primes.\r\ndef primesLessThan(num):\r\n # Initialize some variables\r\n stop = (num-1)\/2\r\n LoP = [2]\r\n oddNums = [True]*stop\r\n i = 0\r\n p = 3\r\n j = num\r\n\r\n #Begin sieving\r\n while math.pow(p, 2)< num:\r\n # Check for prime\r\n if oddNums[i] == True:\r\n LoP += [p]\r\n j = int((math.pow(p, 2)-3))\/2\r\n\r\n #sift on p\r\n while j < stop:\r\n oddNums[j] = False\r\n j += p\r\n\r\n i += 1\r\n p += 2\r\n\r\n # Get the remaining primes\r\n while i < stop:\r\n if oddNums[i] == True:\r\n LoP += [p]\r\n\r\n i += 1\r\n p += 2\r\n\r\n return LoP\r\n\r\n\r\n# Function that returns the first numPrimes primes in a list\r\ndef firstPrimes(numPrimes):\r\n\r\n # Use the Prime Number Theorem here to help figure out about where the\r\n # last prime is\r\n\r\n # First (slightly over)estimate where the numPrimes prime is using the Prime Number Theorem.\r\n estimate = int(numPrimes*(math.log(numPrimes) + math.log(math.log(numPrimes))))\r\n\r\n # Get a list of the primes less than the estimate\r\n bigList = primesLessThan(estimate)\r\n\r\n # Cut the list at the number needed and return that\r\n result = bigList[:numPrimes]\r\n\r\n return result\r\n\r\n# This function determines is an integer input is prime.\r\n# The method used is trial division. The runtime of this\r\n# function is bounded by (Num^(1\/2)). It beats the\r\n# Miller-Rabin primality test for numbers around less than\r\n# 1,000,000 (in terms of runtime).\r\ndef isPrime(Num):\r\n\r\n\tif (Num == 2):\r\n\t\treturn True\r\n\tif (Num % 2 == 0):\r\n\t\treturn False\r\n\r\n\tsqrtNum = int(math.sqrt(Num)) + 1\r\n\r\n\tfor x in range(3, sqrtNum, 2):\r\n\t\tif Num % x == 0:\r\n\t\t\treturn False\r\n\r\n\treturn True\r\n\r\n# This is a python implementation of the Miller-Rabin\r\n# primality test. Trial division beats the Miller-Rabin \r\n# method for numbers under 1,000,000, with numchecks = 10\r\n# (actually a relatively small value)\r\ndef probIsPrime(num, numChecks):\r\n # Some optimizations\r\n if num == 2:\r\n return True\r\n\r\n if num % 2 == 0:\r\n return False\r\n\r\n # Here I use a list of the first 100 primes to use\r\n # as bases when checking primality. This will allow for\r\n # accurate calculations for primes of any reasonable size\r\n # (or even an unreasonable size, like 10^100)\r\n LoP = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \r\n 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \r\n 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, \r\n 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, \r\n 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, \r\n 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, \r\n 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, \r\n 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, \r\n 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, \r\n 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]\r\n i = 0\r\n\r\n # Unfortunately, using numbers greater than num for checking\r\n # causes errors, so some checking is necessary here to ensure\r\n # accuracy\r\n if (num < LoP[numChecks]):\r\n LoP = range(2, num)\r\n\r\n # The meat of the computation\r\n while numChecks > 0:\r\n check = LoP[i]\r\n i += 1\r\n\r\n # Be careful not to index out of the list of primes...\r\n if (i == len(LoP)):\r\n i = 0\r\n\r\n if not strongPseudoprimeTest(num, check):\r\n break\r\n\r\n numChecks -= 1\r\n\r\n return numChecks == 0\r\n \r\n# Function to check primality. It effectively employs Fermat's\r\n# Little Theorem in a creative way to deterimine if a number,\r\n# (the check) demonstrates the compositeness of a number (the num).\r\ndef strongPseudoprimeTest(num, check):\r\n\r\n # Initialize some helpful variables, nice names are unnecessary.\r\n d = num - 1\r\n s = 0\r\n numLessOne = num - 1\r\n\r\n # If d is even divide it by two and increment s\r\n while d % 2 == 0:\r\n d \/= 2\r\n s += 1\r\n \r\n t = pow(check, d, num)\r\n\r\n if ((t == 1) or (t == numLessOne)):\r\n return True\r\n\r\n s -= 1\r\n while s > 0:\r\n s -= 1\r\n\r\n t = pow(t, 2, num)\r\n\r\n if (t == numLessOne):\r\n return True\r\n\r\n return False\r\n\r\n# Solution: 104743\r\n\r\n<\/pre>\nFeedback is always appreciated!<\/p>\n","protected":false},"excerpt":{"rendered":"
The Problem: What is the 10 001st prime number? My Solution (in Python): # Author: Will Clausen # # Date: Jan 7, 2013 # # This program will solve Problem 7 from Project Euler import math import time # This function solves problem 7 from Project Euler. # This function uses a primality tester implemented […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[9,26,19],"class_list":["post-105","post","type-post","status-publish","format-standard","hentry","category-project-euler-solutions","tag-january2013","tag-project-euler-problem-7","tag-project-euler-solution"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/105","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=105"}],"version-history":[{"count":4,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/105\/revisions"}],"predecessor-version":[{"id":109,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/105\/revisions\/109"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=105"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=105"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=105"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}