筛法（挨拉托色尼筛法）是一种用来求所有小于N的素数的方法。用筛法求素数的基本思想是：把从2到n的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍数，直到根号N的倍数为止，剩余的即为2~N之间的所有素数。用python实现

可以使用标记法实现筛法（Sieve of Eratosthenes），具体步骤如下：

1. 创建一个长度为N+1的布尔数组，表示每个数字的状态，初始化为True（即未被标记）。
2. 从2开始，遍历到根号N，如果当前数字未被标记，则将其所有倍数（除了本身）标记为False（即非素数）。
3. 遍历完毕后，所有未被标记的数字即为素数。

以下是Python代码实现：

import math

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)  # 初始化为True
    primes[0] = primes[1] = False  # 0和1不是素数
    for i in range(2, int(math.sqrt(n))+1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return [i for i in range(2, n+1) if primes[i]]

print(sieve_of_eratosthenes(30))  # 输出小于30的素数

输出结果为：

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

相关问题

筛法（挨拉托色尼筛法）是一种用来求所有小于N的素数的方法。用筛法求素数的基本思想 # 是：把从2到n的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍 数，直到根号N的倍数为止，剩余的即为2~N之间的所有素数。请编一个这样求素数的程序

好的，以下是一个基于挨拉托色尼筛法的求素数的程序示例，使用Python语言实现：

def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while p*p <= n:
        if prime[p] == True:
            for i in range(p*2, n+1, p):
                prime[i] = False
        p += 1
    for p in range(2, n+1):
        if prime[p]:
            print(p)

这个程序使用了一个布尔数组`prime`，初始时将所有元素都置为`True`。从2开始，将它的倍数（不包括它本身）在`prime`数组中标记为`False`，表示它们不是素数。这个过程一直进行到根号`n`的倍数为止。最后，遍历整个`prime`数组，输出所有值为`True`的下标，即素数。

筛法（挨拉托色尼筛法）是一种用来求所有小于N的素数的方法。用筛法求素数的基本思想# 是：把从2到n的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、5的倍# 数，直到根号N的倍数为止，剩余的即为2~N之间的所有素数。用python语言用筛法求素数

以下是用 Python 实现筛法求素数的代码：

def sieve_of_eratosthenes(n):
    # 创建一个长度为 n+1 的布尔数组，用于标记每个数是否为素数，默认都为 True
    is_prime = [True] * (n+1)
    # 0 和 1 都不是素数，因此将其标记为 False
    is_prime[0] = is_prime[1] = False
    # 从 2 开始遍历数组，如果当前数字是素数，则将其倍数全部标记为 False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    # 将所有标记为 True 的数字添加到结果列表中
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
    return primes

你可以调用 `sieve_of_eratosthenes(n)` 函数来得到小于等于 `n` 的所有素数。例如，如果要得到小于等于 100 的所有素数，可以这样调用：

primes = sieve_of_eratosthenes(100)
print(primes)

输出结果为：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]