python求质数的3种方法

python求质数的三种方法如下：

1. 穷举法：从2开始逐个判断一个数是否为质数，即判断该数能否被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

2. 埃拉托色尼筛选法（埃氏筛）：先创建一个长度为n+1的布尔类型数组，标记所有大于等于2且小于等于n的数为True，然后依次从2开始将其倍数标记为False，最后筛选出所有为True的数，即为质数。具体实现代码如下：

def sieve_erathosthenes(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

    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
    return primes

3. Miller-Rabin测试法：这是一种用于判断给定数是否为质数的概率性算法，对于一个给定的数n，利用随机数进行多次测试，若测试通过则为质数，若未通过则不是质数。具体实现代码如下：

import random

def miller_rabin(n, k):
    def is_witness(a, n):
        t = n - 1
        while t % 2 == 0:
            t //= 2
            x = pow(a, t, n)
            if x == 1 or x == n - 1:
                return False
            while t != n - 1:
                x = pow(x, 2, n)
                t *= 2
                if x == n - 1:
                    return False
        return True

    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False

    for _ in range(k):
        a = random.randint(2, n - 1)
        if is_witness(a, n):
            return False
    return True

以上就是求质数的三种常用方法，可以根据不同的情况和需求选择适合的方法进行使用。