Python用筛法与试除法求100以内的素数

在Python中，可以使用筛法（如埃拉托斯特尼筛法）或试除法（也称为暴力筛选法）来寻找100以内的素数。这里分别简单解释一下这两种方法：

**埃拉托斯特尼筛法**（Sieve of Eratosthenes）：
这是一种古老而有效的算法，步骤如下：
1. 创建一个从2到100的列表，并将所有数字标记为“可能是素数”。
2. 从第一个质数2开始，将2的所有倍数标记为合数（非素数）。
3. 找到下一个未被标记的数（即下一个质数），继续此过程，直到遍历到100。
4. 到最后，剩下的就是100以内的素数。

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return [i for i, prime in enumerate(primes) if prime]

# 使用该函数找到100以内的素数
prime_list = sieve_of_eratosthenes(100)

**试除法**（Trial Division）：
这种方法较简单但也较为慢速，适用于较小范围的查找：
1. 遍历从2到√n（n的平方根）之间的每个数。
2. 对于每个数n，检查它是否能整除100以内的其他数。如果能，那么n就不是素数。
3. 如果n不能整除任何一个数，那么它是素数。

def trial_division_primes(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

# 100以内素数用试除法
prime_list_trial = trial_division_primes(100)