python判断素数的5种方法

好的，下面是 Python 判断素数的五种方法：

1. 蛮力法：从2开始遍历到n-1，如果n能被其中任意一个数整除，则不是素数。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

2. 优化的蛮力法：只需要遍历到n的平方根即可。

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

3. 筛法：从2开始，将2的倍数、3的倍数、4的倍数……都标记为合数，最后没有被标记的数即为素数。

def sieve(n):
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False
    for i in range(2, int(math.sqrt(n))+1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    return primes

def is_prime(n):
    if n <= 1:
        return False
    primes = sieve(n)
    return primes[n]

4. 费马小定理：如果n是素数，那么对于任意a，a^(n-1) mod n = 1。该算法的缺陷是当n不是素数时，结果也可能是1，因此需要进行多次测试。

import random

def power(a, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = (res * a) % p
        a = (a * a) % p
        n >>= 1
    return res

def is_prime(n, k=5):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    for _ in range(k):
        a = random.randint(2, n-2)
        if power(a, n-1, n) != 1:
            return False
    return True

5. Miller-Rabin算法：该算法是费马小定理的一种扩展，可以快速判断一个数是否是合数。该算法的精度可以通过调整参数k来控制，一般取10-20。

import random

def power(a, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = (res * a) % p
        a = (a * a) % p
        n >>= 1
    return res

def is_prime(n, k=10):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    r, d = 0, n-1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randint(2, n-2)
        x = power(a, d, n)
        if x == 1 or x == n-1:
            continue
        for _ in range(r-1):
            x = (x * x) % n
            if x == n-1:
                break
        else:
            return False
    return True

以上就是 Python 判断素数的五种方法，希望对你有所帮助！