python如何求质数

Python中求解质数的问题，通常可以通过以下两种方法来实现：

方法一：试除法

试除法是一种简单的求解质数的方法，其思路是从2开始，依次试除每个数字，判断其是否能被整除，如果不能被整除，则将其加入质数列表中。

以下是使用试除法求解质数的Python代码示例：

def get_primes(n):
    """使用试除法求解质数"""
    primes = []
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, int(i0.5)+1):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    return primes

使用该函数可以获取指定范围内所有的质数，

print(get_primes(100))  # 获取100以内的所有质数

方法二：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更为高效的求解质数的方法，其思路是从2开始，将每个数字的倍数标记为合数，最后剩下的就是质数。

以下是使用埃拉托斯特尼筛法求解质数的Python代码示例：

def get_primes(n):
    """使用埃拉托斯特尼筛法求解质数"""
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
    return primes

使用该函数可以获取指定范围内所有的质数，

print(get_primes(100))  # 获取100以内的所有质数

两种方法都可以有效地求解质数，其中试除法的时间复杂度为O(n^2)，而埃拉托斯特尼筛法的时间复杂度为O(nloglogn)，因此在求解较大范围的质数时，推荐使用埃拉托斯特尼筛法。