优草派  >   Python

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

陈伟杰            来源:优草派

质数是指只能被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):

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

这个函数用来计算一个数的平方根,并向下取整。在寻找质数的过程中,我们只需要判断一个数字是否能被它的平方根以内的数字整除即可。因此,使用isqrt可以帮助我们提高寻找质数的效率。代码如下:

```

import math

for i in range(2, 101):

is_prime = True

for j in range(2, math.isqrt(i) + 1):

if i % j == 0:

is_prime = False

break

if is_prime:

print(i)

```

上述代码中,我们使用了math库中的isqrt函数,将平方根向下取整。然后对于每个数字i,我们遍历2到它的平方根以内的数字,判断它是否能被整除即可。

2.sympy库

sympy是Python中一个专门用来进行符号计算的库,它提供了许多高级的数学功能,包括寻找质数。使用sympy库,我们可以非常方便地打印100以内的所有质数。代码如下:

```

from sympy import *

primes = primerange(1, 101)

print(list(primes))

```

上述代码中,我们使用了sympy库中的primerange函数,将1到100之间的质数打印出来。

综上所述,Python提供了多种方法来打印100以内的质数,其中暴力算法是最基本和最简单的一种方法,但是时间复杂度较高;优化算法可以提高效率,包括质数只与比它小的质数有关系和质数只能是6的倍数加上1或者5。另外,Python的库函数也可以帮助我们更加方便地寻找质数,包括math库中的isqrt函数和sympy库中的primerange函数。

【原创声明】凡注明“来源:优草派”的文章,系本站原创,任何单位或个人未经本站书面授权不得转载、链接、转贴或以其他方式复制发表。否则,本站将依法追究其法律责任。