python判断素数 欧拉筛

以下是Python中判断素数的欧拉筛实现方法：

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

该方法使用了欧拉筛法，可以在$O(n)$的时间复杂度内求出小于等于$n$的所有素数。具体实现方法是，首先将$2$到$n$之间的所有数都标记为素数，然后从$2$开始，将所有素数的倍数标记为合数，直到$n$。在这个过程中，如果一个数$i$是素数，那么它的倍数$j=i*k$（$k$为正整数）一定被之前的素数筛选过了，因此只需要用$i$去筛选它的倍数即可。同时，如果$i$是某个素数$p$的倍数，那么它一定在$p$的筛选过程中被标记为合数了，因此可以直接跳过。

相关问题

欧拉筛法求素数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 eratosthenes(n):
    is_prime = [True] * (n+1)
    primes = []
    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列表来记录每个数是否为素数，初始时所有数都被标记为素数。然后从2开始遍历每个数，如果该数是素数，则将其加入primes列表中，并将其倍数标记为非素数。在将倍数标记为非素数时，可以通过判断当前数和当前素数的乘积是否大于n来提前退出循环，避免不必要的计算。如果当前数能够被某个素数整除，则跳出当前循环，因为该数已经被标记过了。最后返回primes列表即可。