欧拉筛法求素数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必然已经被其它数标记过了。

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

相关问题

欧拉筛法求素数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 中，并将其倍数标记为非素数。在标记倍数的过程中，我们只需要遍历当前已知的素数，因为其他数已经被标记过了。

第1关：欧拉筛法求素数 python

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

def sieve_of_eratosthenes(n):
    # 初始化一个标记数组，默认所有数均为素数
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False

    # 开始筛选，从2开始到根号n
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # 将i的倍数标记为非素数
            for j in range(i*i, n+1, i):
                is_prime[j] = False

    # 收集所有素数
    primes = [i for i in range(n+1) if is_prime[i]]
    return primes

n = int(input("请输入一个正整数n："))
primes = sieve_of_eratosthenes(n)
print(f"小于等于{n}的素数有：{primes}")

这段代码中，我们使用了欧拉筛法来求解小于等于给定正整数n的所有素数。首先，我们初始化一个标记数组is_prime，将所有数均标记为素数。然后，我们从2开始到根号n进行筛选，如果某个数i是素数，那么将其倍数均标记为非素数。最后，收集所有标记为素数的数，即为所求的素数集合。

请注意，以上代码仅为示例，可能在处理较大输入时效率较低。在实际应用中，可以根据具体情况进行优化。