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

  • Post category:Python

下面就是Python求素数的详细攻略,包括两个代码示例的说明。

素数的定义

素数,又称质数,指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。例如:2、3、5、7、11、13、17、19、23、29、31等。

求素数的方法

方法一:逐个判断法

逐个判断法是最基础的一种求素数的方法。除了1和本身,对于一个数n,逐一判断从2到n-1之间有没有数能够整除它,如果找不到,那么n就是素数。

下面是使用逐个判断法求素数的代码示例:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

这里定义了一个is_prime函数,这个函数接受一个参数n,返回一个布尔值,用来判断n是否为素数。在函数中,首先判断n是否小于2,因为小于2的数都不是素数。然后使用for循环对2到n-1之间的所有数进行判断,如果n能够被其中的一个数整除,那么n就不是素数,返回False,否则就是素数,返回True。

这个方法虽然简单易懂,但是效率较低,随着n的增大,判断的次数也会增多。

方法二:埃氏筛法

埃氏筛法是一种较为高效的求素数的方法。它的基本思想是,从2开始,将每个素数的倍数都标记成合数,直到筛子无法再筛下去为止。

下面是使用埃氏筛法求素数的代码示例:

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    return [i for i in range(n + 1) if is_prime[i]]

这里定义了一个sieve_of_eratosthenes函数,这个函数接受一个参数n,返回一个列表,包含了所有小于等于n的素数。在函数中,首先创建一个长度为n+1的布尔数组is_prime,用来记录每个数是否为素数。将0和1标记为False,因为它们都不是素数。然后从2开始循环,如果当前数p是素数,那么将p的倍数都标记为合数。这里使用的是p * p <= n的条件,是因为从2到n的其他素数的倍数,已经被之前的素数筛去了,没有必要再进行判断。最后返回is_prime为True的索引,就是所有小于等于n的素数。

总结

逐个判断法是最基础的求素数方法,虽然简单易懂,但是效率较低。而埃氏筛法则是一种较为高效的求素数方法,其思想是从2开始,逐个筛去合数,最后留下的就是素数。在实际应用中,可以根据情况选择适合自己的方法来求素数。