埃拉托色尼筛求不大于n=25的质数序列 Python

埃拉托色尼筛（Sieve of Eratosthenes）是一种古老而高效的找出一定范围内所有质数的经典算法。以下是使用Python实现一个不超过n（这里设为25）的质数序列的简单版本：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 初始化一个布尔列表，标记所有数字为质数
    primes[0], primes[1] = False, False  # 0和1不是质数

    for i in range(2, int(n**0.5) + 1):  # 遍历到n的平方根即可，因为大于这个数的因子一定会小于它本身
        if primes[i]:  # 如果i是质数
            for j in range(i*i, n + 1, i):  # 将i的所有倍数标记为非质数
                primes[j] = False

    # 返回大于1且为质数的索引值对应的数字
    return [i for i, is_prime in enumerate(primes) if is_prime and i > 1]

# 输出不大于25的质数序列
print(sieve_of_eratosthenes(25))

相关问题

埃拉托色尼筛子python

以下是一个简单的Python程序，用于生成埃拉托色尼筛子：

def sieve(n):
    """
    生成埃拉托色尼筛子
    """
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i ** 2, n + 1, i):
                primes[j] = False
    return [i for i in range(n + 1) if primes[i]]

# 测试
print(sieve(30))

输出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

该程序使用了埃拉托色尼筛子算法，首先创建一个长度为n+1的布尔数组，初始值为True，表示该位置上的数是素数。然后从2开始遍历数组，如果该位置上的数是素数，则将其倍数的位置上的数标记为非素数。最后遍历数组，将所有标记为素数的数存入一个列表中返回。

实现埃拉托色尼筛python，计算并输出不大于输入数字的所有质数

埃拉托色尼筛法是一种古老而有效的寻找小于或等于给定数值范围内所有质数的经典算法。以下是使用 Python 编程语言实现这个算法的一个版本：

def eratosthenes_sieve(n):
    primes = [True] * (n + 1)  # 初始化一个布尔数组，假设0到n都是质数
    primes[0], primes[1] = False, False  # 0和1不是质数

    for i in range(2, int(n**0.5) + 1):  # 只需检查到√n，因为大于这个数的因子都会有一个较小的配对因子
        if primes[i]:  # 如果i是质数
            for j in range(i*i, n + 1, i):  # 将i的倍数标记为非质数
                primes[j] = False

    # 输出所有的质数
    for num in range(2, n+1):
        if primes[num]:
            print(num)

# 调用函数并传入你要找质数的最大值
n = int(input("请输入一个整数："))
eratosthenes_sieve(n)