大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说使用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 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/20026.html
