埃拉托斯特尼筛法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埃拉托斯特尼筛法的优势

埃拉托斯特尼筛法是一种用于判断一个数是否为素数的高效算法。相较于其他判断素数的方法，它的优势在于可以提前筛选出一定范围内的所有素数，从而减少了判断的次数。在使用埃拉托斯特尼筛法时，我们可以先将从2开始的所有整数进行标记，然后从2开始依次遍历，将遍历到的素数的倍数进行标记，最终剩下的未被标记的数即为素数。这样一来，我们只需要遍历到输入数的平方根即可。