用Python将厄拉多塞筛法表达

素数列表

很好的问题！下面是使用 Python 实现厄拉多塞筛法的代码：

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

n = 50
print("Prime numbers smaller than or equal to", n, "are:")
print(sieve(n))

这里使用了一个布尔型数组 prime[] 来记录每个数是否为素数，一开始默认所有数都是素数，然后从 2 开始遍历，对于每个素数 p，将它的倍数都标记为非素数。最后只需要遍历一遍，将所有标记为素数的数输出即可。

相关问题

Python素数判断

Python素数判断可以使用以下两种方法：

1. 质数判断法：
一个数如果只能被1和它本身整除，那么这个数就是质数。通过遍历2到该数-1的所有数，判断是否能被整除，来判断该数是否为质数。

代码示例：

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

2. 厄拉多塞筛法：
该算法是在一定范围内筛选出所有的质数，而不是单独判断一个数是否为质数。首先将2到n的正整数放入表中，然后在2的上面画一个圆圈，然后把表中所有2的倍数都划掉；第一个既没有画圈又没有被划去的数是3，将它画圈，再把表中所有3的倍数都划去；接下来是5、7、11等质数，不断重复这个过程，直到筛完为止。

代码示例：

def sieve_of_eratosthenes(num):
    primes = [True] * (num+1)
    primes, primes = False, False
    for i in range(2, int(num ** 0.5) + 1):
        if primes[i]:
            for j in range(i*i, num+1, i):
                primes[j] = False
    return [i for i in range(num+1) if primes[i]]

素数python不同方法

有很多不同的方法可以用 Python 生成素数，以下是其中几个常见的方法：

1. 暴力枚举法：

这种方法的思路是从 2 开始遍历所有的自然数，判断其是否为素数。具体实现可以使用两个嵌套的循环，外层循环枚举自然数，内层循环用于判断是否为素数。代码示例：

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def generate_primes(n):
    primes = []
    for i in range(2, n):
        if is_prime(i):
            primes.append(i)
    return primes

2. 厄拉多塞筛法：

这种方法的基本思路是从小到大枚举自然数，如果该数为素数，则将其所有的倍数都标记为合数。具体实现可以使用一个布尔数组来记录每个数是否为素数，初始时所有数都为素数，然后从 2 开始枚举，如果当前数为素数，则将其所有的倍数都标记为合数。代码示例：

def generate_primes(n):
    is_prime = [True] * n
    primes = []
    for i in range(2, n):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, n, i):
                is_prime[j] = False
    return primes

3. 线性筛法：

这种方法是一种优化过的厄拉多塞筛法，其基本思路是从小到大枚举自然数，如果该数为素数，则将其直接加入素数列表，并且将其所有的倍数都标记为合数。如果当前数是某个素数的倍数，则直接跳过。具体实现可以使用一个数组记录每个数的最小素因子，初始时所有数的最小素因子都为自身，然后从 2 开始枚举，如果当前数的最小素因子是自身，则将其加入素数列表，并将其所有的倍数的最小素因子都更新为该素数。代码示例：

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

以上是三个常见的生成素数的方法，实际上还有很多其他的方法可以用于生成素数。