Project Euler Solution 7: 10001st prime
This is part of the Project Euler series, this is about Problem 7: 10001st prime. It is about finding the 10001st prime, just as the title says.
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?
def solution_generator() -> int: return list(itertools.islice(prime_generator(), 10000, 10001))[0]
This takes 1.9 s to produce the correct answer of 104,743. This is way too long and there must be a more clever way to do this. And indeed there is, it is called the Sieve of Eratosthenes which lets you find prime numbers up to a ceiling pretty efficiently. Since I already know the solution I can just use that as the ceiling. Otherwise we would have to run the sieve a few times until we get to the 10001st prime.
def prime_sieve(end: int) -> list[int]: sieve = [True] * end sieve[0] = False sieve[1] = False for i in range(end): if sieve[i]: for factor in itertools.count(2): number = factor * i if number >= len(sieve): break sieve[number] = False primes = [number for number, state in enumerate(sieve) if state] return primes def solution_sieve() -> int: primes = prime_sieve(110_000) return primes[10000]
And this solution just takes 27 ms to compute, so that very likely is the intended answer.