python利用函数求素数方法详解

2024-05-17 01:54| 来源: 网络整理| 查看: 265

下面是Python求素数的完整攻略。

什么是素数？

素数，又称质数，指在大于1的自然数中，除了1和该数本身，无法被其他自然数整除的数。

方法一：暴力枚举

求素数最直接的方法是暴力枚举，即对于每个数，判断它是不是素数。具体的方法是对于一个待判断的数n，从2开始枚举到n-1，依次判断n能否被整除。

示例代码如下：

def is_prime(n): # 如果n小于2，直接返回False if n < 2: return False for i in range(2, n): if n % i == 0: return False return True

该函数接受一个参数n，返回值为True或False，表示n是否是素数。首先判断n是否小于2，是的话返回False，因为按照定义，小于2的数都不是素数。然后从2开始枚举到n-1，如果n能够被任何一个数整除，就返回False，否则返回True。

我们可以用这个函数来列出100以内的素数：

for i in range(100): if is_prime(i): print(i)

输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

这种方法的缺点是时间复杂度较高，因为要枚举从2到n-1的所有数。例如，对于100以内的数，该方法需要判断的数有：

2, 3, 4, 5, ..., 99, 共98个数

当n很大时，判断的数就会变得非常多，效率很低。

方法二：试除法

试除法是一种更高效的求素数方法。它的基本思想是，对于一个待判断的数n，只需要用从2到sqrt(n)的所有素数依次试除即可，如果都不能整除，则n也是素数。

为什么只需要试除从2到sqrt(n)的素数呢？假设n不是素数，则它可以表示为m1*m2的形式，其中m1和m2都在2到n-1之间。如果m1和m2都大于sqrt(n)，则有：

m1 * m2 > sqrt(n) * sqrt(n) = n

这与m1 * m2 = n矛盾，因此至少有一个因子小于等于sqrt(n)。

示例代码如下：

def is_prime_v2(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True

该函数与上面的函数类似，主要的区别在于枚举的范围改为了2到sqrt(n)，并且sqrt(n)用n**0.5的形式计算。

我们可以用这个函数来列出100以内的素数：

for i in range(100): if is_prime_v2(i): print(i)

输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

注意，虽然这个方法比暴力枚举要快，但是当n非常大时，仍然需要计算很多次，速度仍然较慢，因此还有更高效的方法可以使用。

以上就是Python求素数的完整攻略，希望能对您有所帮助。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：python利用函数求素数方法详解 - Python技术站

【本文地址】

今日新闻