python如何取素数
原创Python中的素数查找
Python中查找素数的一个非常基本的方法是使用试错法,即,我们通过遍历从2开始的所有整数,检查它们是否可以被除1和自身以外的任何整数整除,如果不能,那么它就是素数。
这种方法效率不高,因为它需要检查所有的整数,为了提高效率,我们可以使用埃拉托斯特尼筛选法(Sieve of Eratosthenes)算法,这种算法的思想是从2开始,把每一个数的倍数都标记为合数,那么没有被标记的数就是素数。
以下是使用埃拉托斯特尼筛选法查找素数的Python代码:
def sieve_of_eratosthenes(n): """返回小于等于n的所有素数的列表""" is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n0.5) + 1): if is_prime[i]: for j in range(i2, n + 1, i): is_prime[j] = False primes = [] for i in range(n + 1): if is_prime[i]: primes.append(i) return primes 测试代码 print(sieve_of_eratosthenes(30)) # 输出:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
这个函数首先创建一个布尔列表is_prime
,表示每一个数是否为素数,它从2开始,把每一个数的倍数都标记为合数,它返回所有被标记为素数的数。
上一篇:stulist如何定义Python 下一篇:macpro如何安装python