Constraints

• 0 <= n <= 100000
• Return primes in ascending order
• If n = 0, return []
• Use an efficient approach (e.g., sieve or optimized trial division)

Solution

from math import log

def first_n_primes(n: int) -> list[int]:
    """
    Return the first n prime numbers in ascending order.
    Uses a sieve sized via an upper bound for the nth prime and grows if needed.
    """
    if n <= 0:
        return []
    if n == 1:
        return [2]

    # Upper bound for nth prime (Rosser's theorem) for n >= 6:
    # p_n <= n (ln n + ln ln n). Use a small safety offset.
    if n < 6:
        limit = 15
    else:
        nn = float(n)
        limit = int(nn * (log(nn) + log(log(nn))) + 3)

    while True:
        sieve = bytearray(b"\x01") * (limit + 1)
        if limit >= 0:
            sieve[0] = 0
        if limit >= 1:
            sieve[1] = 0
        m = int(limit ** 0.5)
        for p in range(2, m + 1):
            if sieve[p]:
                start = p * p
                sieve[start:limit + 1:p] = b"\x00" * ((limit - start) // p + 1)
        primes = [i for i, is_prime in enumerate(sieve) if is_prime]
        if len(primes) >= n:
            return primes[:n]
        # If the bound was too small, grow and retry
        limit = int(limit * 1.5) + 1

Explanation

Time complexity: O(L log log L), where L is the final sieve limit ≈ n (ln n + ln ln n) for n >= 6. Space complexity: O(L).

Hints

1. A sieve is efficient when you know an upper bound for the nth prime.