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 sieve_of_euler(n):
    is_prime = [True] * (n+1)
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if p * i > n:
                break
            is_prime[p * i] = False
            if i % p == 0:
                break
    return primes

这个函数的输入参数是一个正整数n，输出是小于等于n的所有素数。该算法的时间复杂度为O(nloglogn)，空间复杂度为O(n)。

欧拉筛法求素数python用列表

我很高兴回答您的问题。欧拉筛法是一种高效的求素数的算法，其原理是通过筛选法来得到素数，具体实现可以使用Python的列表。下面是一个示例代码：

def prime_sieve(n):
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for prime in primes:
            if i * prime > n:
                break
            is_prime[i * prime] = False
            if i % prime == 0:
                break
    return primes
    
n = int(input("请输入一个正整数："))
print(prime_sieve(n))

该代码中，变量`n`表示要求的素数的范围，函数`prime_sieve(n)`返回这个范围内的所有素数。具体实现是使用一个布尔型的列表`is_prime`来记录每个数是否是素数，如果是素数就加入到`primes`列表中。然后遍历`primes`列表中的素数，将它们的倍数标记为合数，如果当前的数i可以整除一个素数prime，那么就可以跳过后面的检查，因为i*prime必然已经被其它数标记过了。

希望这个代码可以帮到您！