如何用python实现短时间输出大量素数

• 用代码“输出素数”恐怕是所有程序猿的必经之路，笔者最近忽而又听见这个熟悉的词汇，一时兴起写下以下代码。当然，不能只追求简单的实现功能。能否有办法在尽可能短的时间内实现，才是目的。

• 可惜笔者才疏学浅，代码感觉还有很多可以完善的地方，暂时没有了头绪。

• 经试验
  判断100万范围内的素数需要时间如图

  
  判断100万的素数.jpg

  输出100万范围内的素数需要时间如图

  
  输出100万内的素数.png

• 下面是程序的完整代码

import datetime
first = datetime.datetime.now()

def main():
    print("欢迎进入素数输出界面（输出范围内所有素数）")
    n = int(input('请输入查询数字（n>=1）：'))

    r = [1,0,0,0,1,0]*(n//6 +1)
    r.insert(0,"0")         #为了索引和实际值能对应相等，便于思考
    r[1] = 0
    r[2] = 1
    r[3] = 1

    for i in range(5,int(n**0.5),2):
        if r[i] == 1:
            for j in range(i*i,n+1,2*i):
                r[j] = 0

    for i in range(1,n+1):
        if r[i] == 1:
            print(i)

    two = datetime.datetime.now()
    print("开始查询时间：",first)
    print("结束查询时间：",two)

if __name__ == '__main__':
    main()

你所要认识的黑科技大法

1、孪生素数

• 孪生素数：是指相差2的素数对，例如3和5，5和7，11和13…
• 素数两性定理：大于3的素数只分布在6n-1和6n+1两数列中

发现没有发现没有，我们再也不用遍历每个自然数，因为素数只存在于 6n+1/6n-1，只需要输出遍历 6n+1/6n-1位置的数。每6个自然数组内，只遍历其中两个数，也就是说我们直接把判断时间缩为原来的1/3

2、吹蜡烛法

• 传统的素数判断是逐个遍历n-1个数，看是否存在整除，得出是否为素数。假设n个数，就是遍历n*(n-1)/2，随n的增大，遍历次数是疯狂增加，效率及其低下。
• 吹蜡烛法就是先根据孪生素数定义，把可能为素数的值设为1，为蜡烛点燃状态。设置长列表（对内存有要求，有待完善），最后可遍历索引判断素数，直接输出所有素数，减少循环语句的使用

3、倍数找因数法

• 设置两层循环，第一层遍历得出√n内所有素数。第二层则是为了找出在第一层为素数的数值， 把其平方及其更大倍数的数值找出来，标记为“0”。
• 可能有点绕口，举个栗子。
  7为第一层循环找出的素数，进入第二层循环，是为了把49、56、63等合乎范围内的数值标记为合数，因为它们都存在一个因数“7”。
• 标记过后的数值，因为不可能为素数，在经过第一层循环后直接跳过第二层，诸如此类，可以省略大量时间。再省略偶数遍历第一层，只遍历倍数的第二层，整体时间倍数般缩减（爽，(っ•̀ω•́)っ✎⁾⁾ 我爱学习）

当然由于输出语句，把素数都输出的时间跟传统方法也不会差多少（emmmm....无奈脸）