下面就是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开始,逐个筛去合数,最后留下的就是素数。在实际应用中,可以根据情况选择适合自己的方法来求素数。