欧拉筛法O(N)代码

欧拉筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有质数的算法，它的时间复杂度确实是线性的，即O(N log log N)，但它可以优化为O(N)的空间复杂度，通过只保留每个合数因子的位置信息。

以下是简化版的欧拉筛法的Python代码实现：

def eratosthenes_sieve(n):
    is_prime = [True] * (n+1)
    p = 2
    while p**2 <= n:
        if is_prime[p]:
            # 将p的倍数标记为非质数
            for i in range(p**2, n+1, p):
                is_prime[i] = False
        p += 1
    
    primes = []
    for p in range(2, n+1):
        if is_prime[p]:
            primes.append(p)
    
    return primes

# 使用示例
primes_up_to_50 = eratosthenes_sieve(50)
print(primes_up_to_50)

相关问题

欧拉筛法求素数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 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，则跳出内层循环，避免重复标记。最后返回质数列表即可。

--相关问题--: