python应用 ---筛法求质数的妙用

求质数的的方式大概分两类：筛法与试除法

筛法

先假定所有的数都是质数，然后通过筛选法去除非质数，剩下的就是质数了。

举个例子：
2~100内的数中
（1）2为质数，那么2的倍数一定不是质数
（2）3为质数，那么3的倍数也不是质数
（3）5为质数，那么5的倍数也不是质数
这里面有一个原理：每个合数必然有一个最小素数因子。如果某个数没有小于自身的素数因子，那么这个数就是素数。

L1=[]
for _ in range(n+1):L1.append(True)L1[0]=False  #排除0和1，从2开始求质数L1[1]=False
for i in range(2,n+1):if L1[i]:print(i)j=i+iwhile j <= n:L1[j]=Falsej+=1	

试除法

试除法比较粗暴，就是对每个数进行试除，不过在除数上可以优化
（1）比如所有的除了2以外的质数都是奇数，因此对于2以外的偶数（因为2也是质数），我们直接跳过，不用进行取余运算
（2）还有一个就是合数a的因子都是成对出现的，因为有了一个因子x必然有另外一个因子y与其相乘才能得到此合数，并且这个较小的因子必然小于√a，
所以在进行试除时，只需要除到√a即可
（3）在进行试除时，我们发现任何非质数的因子都是由更小的质数因子相乘得到的。比如4=2*2，6=2*3等等，
也就是说，我们既然已经进行了a%2的运算，那就没必要再进行a%6的运算了。
所以最终得到一个结论：我们只需要对小于√a这个区间内的质数进行试除即可。
（4）在遍历的过程中，小于a的质数已经计算出来了，可以先存储起来。再进行a是否是质数的运算时，可以利用前面已经计算出来的质数进行试除。
这就叫用空间换时间。

质数分布公式
在[2,x]区间中，质数的个数大约为： x ln ⁡ x \frac{x}{\ln x} lnxx​个，并且这个x越大，这个估值就越准，x较小时，一般误差小于15%，因此在进行实际计算时可以将x的值提高15%。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！