Created
August 20, 2011 23:06
-
-
Save evansneath/1159803 to your computer and use it in GitHub Desktop.
Nth Prime
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def nth_prime(n): | |
"""Finds the nth prime number. | |
Arguments: | |
n: The index of the saught after prime number. | |
Returns: | |
The value of the nth prime number. | |
""" | |
prime_table, counter = [], 2 | |
prime_number, top, last = 0, 10000000, 0 | |
while (counter <= top): | |
# build the list where one means nonprime, zero means prime | |
prime_table.append(0) | |
counter = counter + 1 | |
counter = 2 | |
while prime_number < n: | |
# if that number has not been tagged as nonprime then... | |
if (prime_table[counter - 2] == 0): | |
multiplier = 2 | |
tmp = multiplier * counter | |
while (tmp <= top): | |
# mark the temporary value as nonprime | |
prime_table[tmp - 2] = 1 | |
multiplier = multiplier + 1 | |
# change temp to next multiple value | |
tmp = multiplier * counter | |
prime_number = prime_number + 1 | |
last = counter | |
counter = counter + 1 | |
return last |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment