素数筛

def sieve_of_eratosthenes(limit: int) -> list[int]:
    """Return list of all primes up to limit."""
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= limit:
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
        i += 1
    return [n for n, p in enumerate(is_prime) if p]

primes = sieve_of_eratosthenes(100)
print(primes)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...]
print(f"Count: {len(primes)}")  # Count: 25