输入正整数n求不大于n的全部质数python

为了编写一个Python程序，用于输入一个正整数n并找出所有小于或等于n的质数，我们可以使用著名的埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种通过遍历从2到n的数字，并标记其倍数作为非质数的方法。以下是简单的实现：

def find_primes(n):
    # 初始化一个布尔列表，所有元素都设为True表示它们都是潜在的质数
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False  # 0和1不是质数

    # 遍历从2开始到sqrt(n)，将每个素数的倍数标记为非质数
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):  # 跳过已标记的非质数
                primes[j] = False

    # 返回大于1且为真的索引，即质数
    return [i for i in range(2, n+1) if primes[i]]

# 示例使用
n = int(input("请输入一个正整数: "))
result = find_primes(n)
print(f"小于等于{n}的所有质数有：{result}")