筛选法求素数python

筛选法（Sieve of Eratosthenes）是一种用于求解素数的经典算法。它的基本思想是从2开始，将所有的倍数标记为合数，直到遍历完所有的数。剩下未被标记的数即为素数。

以下是使用Python实现筛选法求素数的代码示例：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记是否为素数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是素数

    # 从2开始遍历到sqrt(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

# 示例：求解100以内的素数
primes = sieve_of_eratosthenes(100)
print(primes)

运行以上代码，将会输出100以内的所有素数。

相关问题

python筛选法求素数

Python代码：

def sieve_of_eratosthenes(n):
    """
    运用筛选法求出小于等于n的所有素数
    """
    # 初始化标记数组
    prime_flags = [True] * (n+1)
    # 首先排除0和1
    prime_flags[0] = prime_flags[1] = False
    # 从2开始筛选
    for i in range(2, int(n**0.5)+1):
        if prime_flags[i]:
            # 如果i是素数，则将i的倍数标记为合数
            for j in range(i**2, n+1, i):
                prime_flags[j] = False
    # 将标记为素数的数存入列表中
    primes = [i for i in range(2, n+1) if prime_flags[i]]
    return primes

函数`sieve_of_eratosthenes(n)`运用筛选法求出小于等于n的所有素数，并将它们存入一个列表中并返回。

筛选法的思路是先生成一个标记数组，将所有数标记为素数。然后从2开始，一个一个地筛选。对于每个素数i，将i的倍数标记为合数，直到大于n。最后，剩下的素数即为所有小于等于n的素数。

时间复杂度：$O(n\log\log n)$（因为 $1\times2,1\times 3,\ldots,1\times n$共有 $n-1$ 个数要判断，$2\times2,2\times3,\ldots,$同理；而 $k\times k$ 开始所有倍数均已经在 $2\times k,3\times k,\ldots,(n/k)\times k$ 中判断过了，为避免重复判定，在 $k>\sqrt n$ 时直接跳过。）

Python筛选法求素数

Python筛选法求素数是一种常见的求素数的方法。其核心思想是从2开始，依次判断每个数是否为素数，如果是素数，则将其倍数标记为合数，最终留下的就是素数。具体实现可以使用for循环遍历2到N，设每个数都为素数，然后判断每个数是否能被2到i-1的整数整除，如果能，则将其标记为合数，否则就是素数。最后输出所有的素数即可。这种方法的时间复杂度为O(nloglogn)，比较高效。