前言线性筛是一种用于找出小于等于给定数值的一切质数的高效算法，它是一种改良版的埃拉托斯特尼筛法，可以在更短的期间内计算出少量的质数，其有期间复杂度低，空间复杂度低，可裁减性强的好处，当天我们就来给大家解说线性筛的成功，话不多说，我们如今开局！文章目录原理成功序幕原理任何除1外的人造数都可以被质数整除，这是由于若它不含有1和自身以外的因...。
前言
线性筛是一种用于找出小于等于给定数值的一切质数的高效算法。它是一种改良版的埃拉托斯特尼筛法，可以在更短的期间内计算出少量的质数。其有期间复杂度低，空间复杂度低，可裁减性强的好处。当天我们就来给大家解说线性筛的成功。话不多说，我们如今开局！
文章目录
- 原理
- 成功
- 序幕
原理
任何除1外的人造数都可以被质数整除，这是由于若它不含有1和自身以外的因子，则它是质数，被自身整除，否则对其1和自身以外的因子启动雷同探讨，即可证实它含有素因子。也就是说我们要判定一个数是不是质数就找出它的的最小质因子，假设最小质因子等于它自身，那么它就是质数。反之它就不是质数。
就拿质数2举例，它的倍数除了2以外全都不是质数。
成功
首先我们要先创立一个数组minp用来贮存每个数的最小质因子，而后在创立一个数组prime用来贮存质数。我们须要从2到n（指定的数）范围内挑选进去质数，同时求出各个数的最小质因子，我们刚才得悉2的倍数的最小质因子全都是2,3的倍数的最小质因子也雷同是3，也就是说我们可以经过循环把minp[质数的倍数]的值所有变为该质数的值，这时刻我们或许会发现有些会疑问，比如6是2的倍数也是3的倍数。那么遍历后它的最小质因子不就变成3而不是2了么？没错是这样的，所以我们须要有这样一句判别假设这个数模上如今遍历到质数等于0我们就中止循环，或许当这个数的最小质因子等于目前遍历到的质数时就中止循环，这样就可以处置刚才的疑问（这句话最难看着代码读不然不好了解）。那么我们上代码！
include<stdio.h>
int mainint prime100 0 //质数int minp101 0 //最小质因子int cnt 0for int i 2 i 100 iif 
minpi 0minpi iprimecnt ifor int j 0 j cnt jint p primejif i p 100breakminpi p pif minpi pbreak//if(i%p==0) //用这个也可以//break;for int i 0 i cnt iprintf"%d " primeireturn 0序幕
当天的线性筛算法就引见到这里，假设感觉博主讲的不错的话请给博主一个关注，点赞，收藏。博主还将继续分享常识，我们下期再见！
