如何在Python中实现埃氏筛法？

在Python中实现埃拉托斯特尼筛法（Sieve of Eratosthenes），你可以按照以下步骤编写代码：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 初始化一个布尔列表表示每个数是否为素数，默认全为True
    p = 2  # 首先考虑2作为第一个素数

    while p * p <= n:  # 只需要检查到√n，因为之后的合数肯定已经有小于它的因子被标记了
        if primes[p]:  # 如果p是素数
            for i in range(p * p, n + 1, p):  # 将p的倍数标记为非素数
                primes[i] = False
        p += 1  # 移动到下一个未被标记的数

    # 输出结果，索引位置为素数，值为True
    prime_numbers = [i for i in range(2, n+1) if primes[i]]
    return prime_numbers

# 示例
n = 30
print(sieve_of_eratosthenes(n))  # 输出2到30之间的素数

这段代码首先创建了一个布尔数组表示从2到n的所有数，然后通过循环逐个排除合数，最后筛选出剩下的素数。

相关问题

python实现埃氏筛法求2～10000素数

埃氏筛法是一种用于求解一定范围内素数的算法。下面是使用Python实现埃氏筛法求解2～10000的素数的代码：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的列表，用于标记数字是否为素数，初始全部为True
    primes = [True] * (n + 1)
    # 将0和1标记为非素数
    primes[0] = primes[1] = False
    
    p = 2
    while p * p <= n:
        # 如果p没有被标记为非素数，则p一定是素数，因此将p及其倍数标记为非素数
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    
    # 返回所有标记为素数的数字
    return [i for i in range(n + 1) if primes[i]]

# 调用函数并打印结果
primes = sieve_of_eratosthenes(10000)
print(primes)

以上代码实现了一个名为`sieve_of_eratosthenes`的函数，该函数接受一个参数`n`，用于指定范围。函数内部使用了一个长度为`n+1`的列表`primes`来标记数字是否为素数，其中初始全部为`True`。然后从2开始，找到一个素数后，将其倍数都标记为非素数。最终，返回所有标记为素数的数字。

在主程序中，调用`sieve_of_eratosthenes`函数并传入10000作为参数，得到2～10000范围内的素数列表，并将其打印输出。

埃氏筛法python

埃氏筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始，将每个素数的倍数标记为合数，直到遍历完所有小于给定范围的数。以下是埃氏筛法的Python实现：

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

    # 从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

使用示例：

n = 100
primes = sieve_of_eratosthenes(n)
print(primes)

这段代码将输出小于等于100的所有素数。