Skip to content

Instantly share code, notes, and snippets.

@GrAndSE
Created April 10, 2013 11:21
Show Gist options
  • Save GrAndSE/5353804 to your computer and use it in GitHub Desktop.
Save GrAndSE/5353804 to your computer and use it in GitHub Desktop.
Trying to find a Nth prime number (for a http://projecteuler.net/problem=7)
def get_primes(start, end, primes=[]):
'''Get the numbers starting from start with the count based on primes
'''
sieve = range(start, end)
for prime in primes:
# Get the start value for primes striking
start_value = prime ** 2
if start_value > end:
break
if start_value < start:
num = start / prime
if start % prime:
num += 1
start_value = num * prime
# Strike out complex
for index in xrange(start_value, end, prime):
sieve[index - start] = False
# Get the numbers was not striked out
return [number for number in sieve if number]
def get_prime_by_number(number):
'''Get the n-th prime number'''
primes = [2, 3]
last_num = 0
primes_num = 2
end_value = step = 5
while primes_num < number:
# Get a new step size for prime sieve
last_num = primes_num
primes_num = len(primes)
last_prime = primes[primes_num - 1]
start_value = end_value
end_value = last_prime ** 2
if primes_num > last_num:
step *= (number - primes_num) * 1. / (primes_num - last_num)
if start_value + step < end_value:
end_value = start_value + int(step)
else:
step = end_value - start_value
# Get new primes
primes += get_primes(start_value, end_value, primes)
return primes[number - 1]
print get_prime_by_number(100001)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment