如何用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....无奈脸）
