筛法求素数质数
埃拉托斯特尼筛法 ，简称 埃氏筛 或 爱氏筛 ，是一种由希腊数学家 埃拉托斯特尼 所提出的一种简单 检定素数 的算法。要得到自然数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]本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-01-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读