使用Python判断素数

引言

素数是指在大于1的自然数中，除了1和本身以外，不能被其他自然数整除的数。判断一个数字是否为素数一直是计算机编程领域中一个很热门的话题。Python 作为一门强大且易学的编程语言，提供了多种方法用于判断素数。本文将介绍多种 Python 算法来判断一个数字是否是素数。

python判断素数

算法中比较常见的是反复模除法，如果某个数在2到它本身-1的范围内没有被整除，就可以称这个数字是素数。

def is_prime(num):
    if num < 2:
        return False
    for x in range(2,num):
        if num % x == 0:
            return False
    return True

python判断素数的方法

除了上面的反复模除法以外，还有其他常见的素数检测算法，包括：埃拉托色尼素数检测、费马素性检测、波兰素数检查、 米勒-拉宾素性检验等等。

1、埃拉托色尼素数检测

埃氏筛法是由希腊学者埃拉托色尼提出的，它可以用于找出一定范围内的所有素数。它的算法思想是：如果一个数是素数，则它的倍数均不是素数。这一思想也称为“素数筛法”。具体实现如下：

def prime_eratosthenes(n):
    prime = [True] * n
    p = 2
    while p*p < n :
        if prime[p] == True:
            for x in range(p*p, n, p):
                prime[x] = False
        p += 1
    return [i for i in range(2,n) if prime[i] == True]

2、费马素性检测

费马素性检测是基于费马小定理的，即a^(n-1) ≡ 1 (mod n)。对于a,n互质且n是素数时，上面的定理是成立的，反之则不一定。如果你取a是2或3等小于n的数字，那么求a^(n-1)是可行的，但是，对于比较长的n来说，计算量非常大，不怎么实用。

def fermat_prime(num):
    if num == 2:
        return True
    elif num % 2 == 0:
        return False
    else:
        for i in range(0, 100):
            if pow(2**i, num-1, num) != 1:
                return False
        return True

3、波兰素数检查

波兰素数检查是一种基于椭圆曲线的素性检测算法，可以用于找出一定范围内的所有素数，比如说在开源的Open SSL、Open SSH等大型开源软件中都有它的身影。具体原理涉及到较多数论和代数知识，这里仅提供代码实现：

def pow_mod(x, k, m):
    if k == 0: 
        return 1
    elif k % 2 == 0:
        return pow_mod(x, k/2, m)**2 % m
    else:
        return pow_mod(x, k - 1, m) * x % m

def lucas_lehmer_primer(num):
    if num <= 2:
        return num == 2
    elif num % 2 == 0:
        return False
    else:
        n = num - 1
        s, d = 0, n
        while d % 2 == 0:
            s += 1
            d //= 2
        m = 2 ** n - 1
        for a in range(2, n):
            am = pow_mod(a, m, num)
            if am == 1 or am == n:
                continue
            for i in range(0, s - 1):
                am = pow_mod(am, 2, num)
                if am == n:
                    break
            else:
                return False
        return True

python素数判断并输出

def print_prime(max):
    for num in range(2,max+1):
        if is_prime(num):
            print(num, end=" ")

python判断素数并求和

def sum_prime(max):
    prime_sum = 0
    for num in range(2, max+1):
        if is_prime(num):
            prime_sum += num
    return prime_sum

python判断素数代码

判断一个数是否是素数，最常用的方法是反复模除法。该方法通过判断数字x是否能被2到x-1之间的所有数字整除，来判断x是否为素数。

def is_prime(num):
    if num < 2:
        return False
    for x in range(2,num):
        if num % x == 0:
            return False
    return True

python判断是否为素数

判断一个数是否是素数，最简单的方法是排除法：从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

python判断素数的5种方法

上述内容已经介绍了5种Python判断素数的方法，分别是:

• 反复模除法
• 埃拉托色尼素数检测
• 费马素性检测
• 波兰素数检查
• 排除法

python判断1~100素数

for num in range(1,101):
    if is_prime(num):
        print(num, end=" ")

用python编写质数的判断

检查一个数字是否是质数，方法与判断素数类似，只是要把判别条件由“是否不能被(2, num)内的整数整除”改为“是否不能被2的倍数和(3, num)内奇数整除”。

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