Python使用集合实现筛选法求素数

筛选法是一种常用的求素数的方法，可以通过Python中的集合来实现。筛选法的核心思想是从小到大枚举每个数，如果这个数是素数，则将它的倍数全部从集合中删除。

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

def sieve_of_eratosthenes(n):
    primes = set(range(2, n+1))  # 初始化集合，从2到n
    for i in range(2, int(n**0.5)+1):  # 枚举2到根号n的数
        if i in primes:  # 如果i是素数
            for j in range(i*i, n+1, i):  # 将i的倍数从集合中删除
                primes.discard(j)
    return primes

在上述代码中，首先初始化一个包含2到n的集合，然后从2到根号n的数枚举每个数i，如果i是素数，则将i的倍数从集合中删除。最终返回集合中剩余的素数。

使用示例：

primes = sieve_of_eratosthenes(100)
print(primes)  # 输出集合中的素数

输出结果：

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

这段代码可以求出小于等于n的所有素数，时间复杂度约为O(nloglogn)。