欧拉筛法求素数python

可以使用以下代码实现欧拉筛法求素数：

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

其中，is_prime 是一个数组，用来记录每个数是否为素数。我们从 2 开始，依次判断每个数是否为素数，如果是素数，就将其加入 prime_list 中，并将其倍数标记为非素数。在标记倍数的过程中，我们只需要遍历当前已知的素数，因为其他数已经被标记过了。

相关问题

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`数组中的所有素数即可。

Python欧拉筛法求素数

Python欧拉筛法求素数的代码如下：

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

这个算法的时间复杂度为O(n)，空间复杂度为O(n)。它的基本思路是先将所有数标记为质数，然后从2开始遍历到n，如果当前数是质数，则将它的倍数标记为合数。具体实现时，可以用一个布尔数组is_prime来记录每个数是否为质数，用一个列表prime_list来记录已经筛选出来的质数。在遍历到一个质数i时，将它的倍数i*j（j为质数列表中的元素）标记为合数，并且如果i能够整除j，则跳出内层循环，避免重复标记。最后返回质数列表即可。

--相关问题--: