湖南龙网

  1. 首页 > 生活百科 > >

python如何打印100以内的质数？

生活百科python

质数是指只能被1和它本身整除的正整数 ， 如2、3、5、7等 。在计算机编程中 ， 寻找质数是一个常见的问题 。Python作为一门易学易用的编程语言 ， 也提供了多种方法来打印100以内的质数 。
一、暴力算法

python如何打印100以内的质数？

文章插图
暴力算法是最基本的寻找质数的方法 ， 它的思路是对每个数字进行一次判断 ， 看它是否能被除了1和它本身以外的数整除 。在Python中 ， 可以使用for循环来实现：
```
for i in range(2, 101):
is_prime = True
for j in range(2, i):
【python如何打印100以内的质数？】if i % j == 0:
is_prime = False
break
if is_prime:
print(i)
```
上述代码中 ， 外层的for循环遍历2到100之间的所有数字 ， 内层的for循环判断该数字是否为质数 。如果该数字能被2到i-1之间的任意一个数整除 ， 则不是质数 ， 否则是质数 。
然而 ， 暴力算法的时间复杂度为O(n^2) ， 当n很大时 ， 程序运行时间会非常长 。
二、优化算法
为了提高寻找质数的效率 ， 可以采用一些优化算法 。其中 ， 较为常用的优化算法有：
1.质数只与比它小的质数有关系 。
这个算法的思路是 ， 如果一个数是质数 ， 那么它一定不能被比它小的质数整除 。因此 ， 我们只需要记录已知的质数 ， 然后对每个数字判断它是否能被已知的质数整除即可 。代码如下：
```
primes = [2]
for i in range(3, 101):
is_prime = True
for p in primes:
if i % p == 0:
is_prime = False
break
if is_prime:
primes.append(i)
print(primes)
```
上述代码中 ， 我们先定义一个列表primes ， 用来存储已知的质数 。然后 ， 对于每个数字i ， 我们遍历已知的质数p ， 如果i能被p整除 ， 则说明i不是质数 ， 直接跳出循环 。如果遍历完所有已知的质数 ， 仍然没有发现i能被整除的情况 ， 则说明i是质数 ， 将它加入primes列表中 。
2.质数只能是6的倍数加上1或者5 。
这个算法的思路是 ， 除2和3以外的质数一定是6的倍数加上1或者5 。因此 ， 我们可以遍历所有6的倍数加上1或者5的数字 ， 然后判断它是否为质数 。代码如下：
```
primes = [2, 3]
for i in range(5, 101, 6):
is_prime = True
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
is_prime = False
break
if is_prime:
primes.append(i)
for i in range(7, 101, 6):
is_prime = True
for j in range(2, int(i ** 0.5) + 1):
if i % j == 0:
is_prime = False
break
if is_prime:
primes.append(i)
print(primes)
```
上述代码中 ， 我们先定义一个列表primes ， 用来存储已知的质数 。然后 ， 对于所有6的倍数加上1或者5的数字i ， 我们遍历2到i的平方根之间的所有数字j ， 如果i能被j整除 ， 则说明i不是质数 ， 直接跳出循环 。如果遍历完所有可能的因子 ， 仍然没有发现i能被整除的情况 ， 则说明i是质数 ， 将它加入primes列表中 。
三、库函数
除了自己编写算法寻找质数以外 ， Python还提供了一些库函数来帮助我们寻找质数 。其中 ， 比较常用的库函数有：
1.math.isqrt

推荐阅读


上一篇：如何实现python汇率转换代码？

下一篇：Django后端分离 使用element-ui文件上传方式