Euler 7

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #7 statement is —

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 10001st prime number?

A sieve finds all the primes up to a limit in one pass. For the nth prime, $n(\log n + \log\log n)$ is an upper bound when $n \ge 6$, so the sieve can be sized without guessing or repeatedly growing it.

from math import ceil, isqrt, log

n = 10_001
limit = ceil(n * (log(n) + log(log(n))))
sieve = bytearray(b"\x01") * (limit + 1)
sieve[:2] = b"\x00\x00"

for prime in range(2, isqrt(limit) + 1):
    if not sieve[prime]:
        continue

    start = prime * prime
    count = (limit - start) // prime + 1
    sieve[start : limit + 1 : prime] = b"\x00" * count

primes = (number for number, is_prime in enumerate(sieve) if is_prime)
for _ in range(n - 1):
    next(primes)

print(next(primes))

Multiples below prime * prime were already crossed out by smaller primes. The answer is 104743; for sieve limit $L$, it runs in $O(L\log\log L)$ time and $O(L)$ space.