埃拉托斯特尼筛法python

埃拉托斯特尼筛法是一种用于求解质数的算法，其基本思想是从小到大枚举每一个质数，将其所有的倍数都标记为合数。具体的 Python 实现如下：

def eratosthenes(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    return [x for x in range(n+1) if prime[x]]

其中，prime 数组用于记录每个数是否为质数。初始时，所有数都被认为是质数。然后从 2 开始枚举每个质数，将其所有的倍数标记为合数（即将 prime 数组中相应位置设为 False）。最后将 prime 数组中值为 True 的下标返回即可。这些下标即为小于等于 n 的所有质数。

相关问题

埃拉托斯特尼筛法判断素数的程序python

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于判断素数的经典算法。下面是一个使用Python实现的埃拉托斯特尼筛法的程序：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记数字是否为素数
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False

    # 从2开始遍历到根号n
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # 将i的倍数标记为非素数
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    # 收集所有素数
    primes = [i for i in range(n+1) if is_prime[i]]
    return primes

# 示例：打印出100以内的所有素数
primes = sieve_of_eratosthenes(100)
print(primes)

这个程序首先创建了一个长度为n+1的布尔数组is_prime，用于标记数字是否为素数。然后从2开始遍历到根号n，如果当前数字i是素数，则将其倍数标记为非素数。最后，收集所有标记为素数的数字，即为所求的素数列表。

python用埃拉托斯特尼筛法编写判断素数的程序

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于判断素数的经典算法。下面是使用Python编写的埃拉托斯特尼筛法判断素数的程序：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记数字是否为素数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    # 从2开始遍历到根号n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # 将i的倍数标记为非素数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 收集所有素数
    primes = [i for i in range(n + 1) if is_prime[i]]
    return primes

# 示例：判断100以内的素数
primes = sieve_of_eratosthenes(100)
print(primes)

这段代码使用了一个布尔数组 `is_prime` 来标记数字是否为素数。首先将数组中的所有元素初始化为 `True`，然后从2开始遍历到根号n，如果当前数字是素数，则将其倍数标记为非素数。最后，收集所有标记为素数的数字，即为所求的素数列表。