def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 创建一个布尔列表，初始时所有元素设为True
    p = 2
    while p * p <= n:
        # 如果 primes[p] 未被标记为 False, 则是一个质数
        if primes[p]:
            # 更新所有 p 的倍数，从 p*p 开始标记为 False
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p+=1
        while primes[p]==0:
            p+=1

    # 收集所有质数
    prime_numbers = [p for p in range(2, n + 1) if primes[p]]
    return prime_numbers


# 测试算法
n = 10000
print(f"小于等于 {n} 的所有质数: {sieve_of_eratosthenes(n)}")