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

用筛法和试除法可以找到100以内的素数。其中，筛法是通过先列出2到100之间的所有自然数，然后从2开始，将每个素数的倍数都标记为合数，直到100以内的所有素数都被找到为止；试除法则是从2开始，依次将2到根号n之间的所有自然数作为除数，如果n不能被其中任何一个数整除，就说明n是素数。

相关问题

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)

用去除偶数法编写python代码，实现求除100以内所有素数的功能

好的，以下是使用去除偶数法编写的Python代码，可以实现求解100以内所有素数的功能：

# 去除偶数法求解100以内素数
primes = [2]  # 2是唯一的偶质数，先加入列表中
for i in range(3, 101, 2):  # 从3开始，每次加2，枚举奇数
    is_prime = True  # 初始假设i是质数
    for j in range(2, int(i ** 0.5) + 1):  # 枚举2到i的平方根之间的数
        if i % j == 0:  # 如果i能被j整除
            is_prime = False  # i不是质数
            break  # 退出内层循环
    if is_prime:  # 如果i是质数
        primes.append(i)  # 将i加入列表中

# 输出结果
print("100以内的素数为：", end="")
for prime in primes:
    print(prime, end=" ")

运行结果如下所示：

100以内的素数为：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