def is_prime(n):
#if n < 2: return False
#if n == 2: return True
#if n & 1: return False
for i in range(3,int(n**.5)+1,2):
if not n%i:
return False
return True
def prime_list(n):
primes = [2,3,5,7,11,13]
i = max(primes) + 2
while len(primes) < n:
if is_prime(i):
primes.append(i)
i+=2
return primes
print max(prime_list(10001))
Notice that in the is_prime function, I have made it faster by removing tests that will not be necessary for the range it is working with. Un-comment those lines, and one will notice significant slow-downs.
I can comment out these lines in my primality test, because I am:
- not testing primality of numbers less than two
- not testing two at all
- not testing any even numbers
EDIT:
After doing some research, I found this awesome prime number generator:
def gen_primes():
D = {}
q = 2
while True:
if q not in D:
yield q
D[q * q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
With this is play, here is my new answer:
def nth_prime(n):
return (j for i,j in enumerate(gen_primes()) if i == n-1).next()
0 comments:
Post a Comment