信息学奥赛 试除法：高效筛选素数的算法

题目介绍

素数是指只能被1和自身整除的正整数，例如2、3、5、7等。现在给定一个范围内的整数序列，你需要编写一个算法来筛选出其中的素数。

题目解析

题目要求我们从给定的整数序列中筛选出素数。我们需要设计一个算法来判断一个数是否为素数，并将素数添加到结果集合中。

解题思路

为了判断一个数是否为素数，我们可以使用试除法。对于一个待判断的数x，我们从2开始，一直试除到sqrt(x)为止。如果在这个过程中发现x可被某个数整除，则x不是素数；否则x是素数。

具体的算法如下：

1. 定义一个空集合result，用于存储筛选出的素数。
2. 对于每个待判断的数x，从2开始循环到sqrt(x)，判断x是否能够被这些数整除。
3. 如果x不能被任何数整除，则将x添加到result集合中。
4. 循环结束后，返回result作为结果。

代码实现

import math

def sieve_of_eratosthenes(n):
    primes = []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)

    return primes

# 测试示例
n = 100
result = sieve_of_eratosthenes(n)
print(result)

解题技巧

1. 在试除法中，我们只需要循环到sqrt(x)即可，因为如果存在大于sqrt(x)的因子，那么一定存在小于sqrt(x)的因子。
2. 使用一个布尔数组is_prime来记录每个数是否为素数，初始化为True，然后依次将非素数位置的值置为False，这样可以避免重复判断和减少计算量。

总结

本文介绍了如何使用试除法筛选素数，通过这种方法，我们可以高效地得到一个范围内的素数集合。当处理类似问题时，我们可以考虑使用试除法来判断是否为素数。