5 埃拉托色尼筛选

  埃拉托色尼筛选Sieve of Eratosthenes是最简单的一种质数筛选算法。这种算法我们小学就学过,就是数字写入格子里。然后从2开始,以2为第一个质数,划掉2后面所有2的倍数。划掉2的倍数后,再看下一个没被划掉的数字,作为质数,继续划掉它的倍数。
  用表格做个演示:

步骤 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
初始化 / / 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2的倍数 / / 1 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 /
3的倍数 / / 1 1 / 1 / 1 / / / 1 / 1 / / / 1 / 1 /
5的倍数 / / 1 1 / 1 / 1 / / / 1 / 1 / / / 1 / 1 /
7的倍数 / / 1 1 / 1 / 1 / / / 1 / 1 / / / 1 / 1 /

  代码比较简单:

# _*_ coding:utf-8 _*_

def eratoshenes(n):
    array = [True] * (n + 1)
    array[2] = True
    result = []

    for i in range(2, n):
        if array[i]:
            result.append(i)
            for j in range(i << 1, n + 1, i):
                array[j] = False
    return result


if __name__ == '__main__':
    print(eratoshenes(20))
上一篇:Android学习十一:高德地图使用


下一篇:linux下mysql数据的导出和导入(实用于大数据库)