python高效求解质数
质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。因此对于每个数 x，我们可以从小到大枚举 [2,x−1] 中的每个数 y，判断 y 是否为 xx 的因数。
暴力穷举
n = 151100 k = 0 z = [] for i in range(2,n): for j in range(2,int(i**0.5)+1): # 开方，减少循环的次数 if i%j == 0: break else: k+=1 z.append(z) print(k) # 个数 print(z) # 质数
埃氏筛
如果 x是质数，那么大于 x 的 n 的倍数 2x,3x,… 一定不是质数，
首先生成一个数组用来储存数字是否是质数，默认都是质数，出现一次质数就将它的倍数全部标记为不是质数，
埃氏筛刚开始的运行时间较长，因为要不断的对质数倍数的标记，后面的运行就会越来越快
一亿个数大概不到3分钟就可以找出来所有的质数
结合这个图能够更好的理解
n = 10**8 # 代求的范围中的最大值 k = 0 s = [True for i in range(n)] # 首先默认所有数都是质数 z = [] for i in range(2,n): if s[i]: # 判断是否为质数，如果没有被标记过，就是质数 k+=1 z.append(z) for j in range(i+i,n,i): # 将是指数的倍数的数都改为False s[j] = False print(k) # 个数 print(z) # 质数
时间复杂度 O(nloglogn)
质数筛最少需要一个长度为n的数组进行存储标识
