埃拉托斯特尼筛法求素数
2018 年 10 月 11 日
埃拉托斯特尼筛法求素数
算法
要得到自然数n以内的全部素数,必须把不大于 $\sqrt{n}$ 的所有素数的倍数剔除,剩下的就是素数。 [1]
给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。
python实现
def print_prime(N):
ret = list()
for i in range(2, N):
ret.append(i)
idx = 0
def remove_multiple(n):
for v in ret:
if v%n==0 and v//n > 1:
ret.remove(v)
while ret[idx]*ret[idx] <= N-1:
remove_multiple(ret[idx])
idx+=1
print(ret)
if __name__ == '__main__':
print_prime(10000)