埃拉托斯特尼筛法求素数

• 埃拉托斯特尼筛法求素数
• 算法
• python实现
• 参考

算法

要得到自然数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)

参考

算法说明