By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
A problem of 'prime sieve'.
Check all odd numbers one by one, to see if it is prime, and count.
from math import sqrt
def candidates():
higher_digits = 1
while True:
for i in [1, 3, 7, 9]:
yield higher_digits * 10 + i
higher_digits += 1
def solve(ith):
primes = [2, 3, 5, 7]
cnt = 4
for candidate in candidates():
is_composite = lambda p: candidate % p == 0
less_or_equal_sqrt = lambda p: p <= sqrt(candidate)
if not any( # `any` function will fail fast
map(is_composite, # Check if candidate is composite number
filter(less_or_equal_sqrt, primes))): # Only check primes that is <= sqrt(candidate), to see if it is a factor
primes.append(candidate)
cnt += 1
if cnt >= ith:
break
return primes[ith-1]
solve(6)
solve(10001)