筛法求素数质数

筛法求素数质数

​​埃拉托斯特尼筛法​​​ ，简称 ​​埃氏筛​​​ 或 ​​爱氏筛​​​ ，是一种由希腊数学家 ​​埃拉托斯特尼​​ 所提出的一种简单 检定素数 的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......

python代码如下：

#!/usr/bin/python3.4# -*- coding: utf-8 -*-def divided(array): arrlist = [] for i in range(0, len(array)): if i != 0: if array[i] % array[0] != 0: arrlist.append(array[i]) return arrlist, array[0]def getprimes(number): arrlist = [] for i in range(2, number + 1): arrlist.append(i) primes = [] newarrlist, prime = divided(arrlist) primes.append(prime) while True: array = newarrlist if len(array) == 0: break else: newarrlist, prime = divided(array) primes.append(prime) print(primes)if __name__ == "__main__": number = 120 getprimes(number)

运行结果为：

[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, 101, 103, 107, 109, 113]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。