python素数筛法

素数筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。它的基本思想是从小到大依次遍历每个数字，将其倍数标记为非素数，最终剩下的未被标记的数字即为素数。

以下是使用Python实现素数筛法的示例代码：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1

相关问题

python 用筛法求素数

在Python中，我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来求解一定范围内的所有素数。这是一种古老的算法，通过不断地排除合数来找出剩余的素数。以下是实现该算法的一个基本步骤：

def sieve_of_eratosthenes(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

    # 返回索引对应的值就是素数，列表形式更直观
    return [i for i, is_prime in enumerate(primes) if is_prime]

# 示例
n = 30
print(sieve_of_eratosthenes(n))  # 输出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

在这个函数中，我们首先创建了一个布尔数组`primes`，然后从2开始，将它的倍数标记为非素数。当遍历完2到√n的所有数后，剩下的未被标记的数即为素数。

python欧拉筛法求素数

欧拉筛法是求解素数的一种高效算法，它的基本思想是通过筛去合数来得到素数。下面是Python实现欧拉筛法求素数的示例代码：

def euler_sieve(n):
    primes = []
    is_prime = [True] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for j in range(len(primes)):
            if i * primes[j] > n:
                break
            is_prime[i * primes[j]] = False
            if i % primes[j] == 0:
                break
    return primes

在这个函数中，我们首先创建了一个布尔数组`is_prime`，并将其全部初始化为`True`，表示在开始时所有的数都是素数。然后，我们从2开始遍历到`n`，如果当前这个数是素数，我们就把它加入到`primes`数组中，并且把它的倍数全部标记为合数（即将`is_prime[i * primes[j]]`置为`False`）。

最后，我们返回`primes`数组中的所有素数即可。