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

  • Post category:Python

下面是Python利用函数求素数的详细攻略:

实现思路

  1. 首先确定一个数是否是素数,可以从2到n-1进行遍历,判断是否有因子能够整除该数。
  2. 但是为了减少遍历次数,可以利用数学的方法, 只需要对2到sqrt(n)进行遍历即可,这是因为任意大于sqrt(n)的数a都一定存在一个小于sqrt(n)的因子b,满足a=b∗c。其中c必然也大于sqrt(n),因此不需要再判定。

代码实现

接下来,我们用Python代码实现这个求素数的函数,代码如下:

import math

def is_prime(num):
    # 判断素数
    if num < 2:
        # 素数必须大于1
        return False
    elif num == 2:
        # 2是素数
        return True
    else:
        for i in range(2, int(math.sqrt(num))+1):
            if num % i == 0:
                # num能被i整除,说明num不是素数
                return False
        return True

其中,is_prime函数接收一个整数作为参数,返回一个布尔值,表示这个数是否是素数。首先判断特殊情况:如果这个数小于2,显然它不是素数;如果是2,那么直接返回True,因为2是最小的素数。否则,从2开始到sqrt(num) + 1进行遍历,如果发现有因子能够整除这个数,那么说明它不是素数,否则就是素数。

下面,我们来编写一个求1到n的素数的函数,代码如下:

def get_primes(n):
    # 求1到n的素数
    primes = []
    for i in range(2, n+1):
        if is_prime(i):
            primes.append(i)
    return primes

这个函数接收一个正整数n作为参数,返回一个列表,表示1到n之间的所有素数。在函数内部,我们遍历2到n,调用is_prime函数判断每个数是否是素数,如果是,就将它加入到primes列表中。最后返回primes即可。

总结

以上就是Python利用函数求素数的实现方法。利用函数的方式,我们可以将判断是否是素数的代码封装成一个函数,方便我们在多个地方重复利用。同时,我们还学习了一些数学方法,可以有效减小计算量,优化程序性能。