埃拉托斯特尼筛法判断素数的程序python

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于判断素数的经典算法。下面是一个使用Python实现的埃拉托斯特尼筛法的程序：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记数字是否为素数
    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

# 示例：打印出100以内的所有素数
primes = sieve_of_eratosthenes(100)
print(primes)

这个程序首先创建了一个长度为n+1的布尔数组is_prime，用于标记数字是否为素数。然后从2开始遍历到根号n，如果当前数字i是素数，则将其倍数标记为非素数。最后，收集所有标记为素数的数字，即为所求的素数列表。

相关问题

python用埃拉托斯特尼筛法编写判断素数的程序

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种用于判断素数的经典算法。下面是使用Python编写的埃拉托斯特尼筛法判断素数的程序：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记数字是否为素数
    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

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

这段代码使用了一个布尔数组 `is_prime` 来标记数字是否为素数。首先将数组中的所有元素初始化为 `True`，然后从2开始遍历到根号n，如果当前数字是素数，则将其倍数标记为非素数。最后，收集所有标记为素数的数字，即为所求的素数列表。

3.编写程序判断101-200之间有多少个素数，并输出所有素数。说明：判断素数的方法 很多，大家可以自行选择判断素数的方法。

在Python中，我们可以使用一种常见的方法来编写程序判断101到200之间的素数并输出它们。这里我们采用埃拉托斯特尼筛法（Sieve of Eratosthenes），这是一种用于查找一定范围内所有质数的古老算法。以下是简单的实现步骤：

def find_primes(start, end):
    primes = [True] * (end + 1) # 初始化一个布尔数组
    p = 2
    while p * p <= end:
        if primes[p]: # 如果p是质数
            for i in range(p * p, end + 1, p): # 将p的倍数标记为合数
                primes[i] = False
        p += 1

    # 输出101到200之间的素数
    prime_numbers = [num for num, is_prime in enumerate(primes[start:end+1]) if is_prime]
    print(f"在{start}到{end}之间有 {len(prime_numbers)} 个素数：", prime_numbers)

find_primes(101, 200)

运行上述程序后，它将输出101到200之间所有的素数。