Python求质数的3种方法

在Python中，求质数的方法有很多，本文将会介绍其中的3种方法。

方法1：暴力枚举

暴力枚举是最基础的求质数方法。从2开始遍历到该数的平方根。如果能被整除，则说明该数不是质数，否则该数是质数。

示例：

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

for i in range(1, 101):
    if is_prime(i):
        print(i)

输出结果：

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

方法2：埃拉托色尼筛法

埃拉托色尼筛法是一种较为高效的求质数方法。该算法先将2到n的各个数分别列出来，然后按照从小到大的顺序，每次取出一个质数，然后将能被这个质数整除的数从列表中删除，继续进行下一次循环，直至没有质数为止。

示例：

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

print(sieve_of_eratosthenes(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]

方法3：欧拉筛法

欧拉筛法是一种更高效的求质数方法，它综合了埃氏筛法的思想和线性筛法的优点。该算法的核心是将合数仅且仅被最小质因子筛掉一次。

示例：

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

print(euler_sieve(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]

以上就是本文介绍的Python求质数的3种方法，分别是暴力枚举、埃拉托色尼筛法和欧拉筛法。可以根据实际需要选择合适的方法进行使用。