前言： tldhk屏幕法1、实施例2、代码实现3、若干改进4、改进后代码5、缺点2、欧拉屏(线性屏幕) 1、原理2、代码实现总结
前言tldhk筛法和欧拉筛(线性筛)是快速找到n以内素数的算法，其中tldhk筛法的时间复杂度接近o(nlogn )，欧拉筛(线性筛)的时间复杂度接近o (n )
相关主题： https://leet code-cn.com/problems/count-primes /
一、tldhk筛法筛法是指在1-n序列中，筛去不符合的数，最终保留符合的数。 利用一个规律：合数都是素数的倍数。 从小到大，利用现有素数num筛选掉其k倍，即k*num。 1 .示例初始化表示用红色标记的素数的数组：
-234567891011121314151617181920从素数2出发，删除2的倍数(4、6、8、10、12、14、16、18和20 )。
-23-5-7-9-11-13-15-17-19-
-23-5-7-9-11-13-15-17-19-从素数3中，删除3的倍数(6、9、12、15和18 ) :
-23-5-7---11-13---17-19-然后，将序列中升序的第一个未标记的数字5标记为素数
-23-5-7---11-13---17-19-从素数5中，删除3的倍数(10、15、20 ) :
- 23-5-7---- 11-13---17-19-http://www.Sina.com /
-23-5-7---11-13--- 17-19-2，代码实现intcountprimes(intn ) {vectorbooliscut ) n1}； //筛选标记，真-被筛掉，假-向量图prime； //存储素数的容器for(intI=2； i=n； I ) if (！ iscut[I]((/I=true，即I未被筛除，加上素数prime.push_back(i ) I )； for(intk=2； k n； (k ) /筛I倍数) if ) k*In ) /防止越界break； iscut[k * i]=true； } } } return prime.size ()； //返回素数个数) 3、一些改进1。 在这里筛I的倍数时，倍数k不需要从2开始。 因为凯的时候，i*k已经被筛过了。 例： i=7、k=3、num=7*3=21是在i=3、k=7、num=3*7=21时筛选出来的。 所以k应该从k=i开始。
对于i*iSIZE，判断可以结束，并将阵列中的剩馀未被筛选的整数添加到素数阵列。
4、改进后的代码intcountprimes(intn ) ) vectorbooliscut ) n1； //筛选标记，真-被筛掉，假-向量图prime； //存储素数的容器for(intI=2； i n 1； I ) if (！ iscut[I]}{/iscut[I]=false，即I不被筛掉，加入素数prime.push_back(I )； for(intk=I； k n； k ) (/I的倍数为if(k*In ) ) /越界防止if (k==I ) ) /是I的平方越界，直接将数组中的剩余数加到素数for中(intj=I1； j=n； j () if (！ iscut[j](prime.push_back ) j； (} i=n 1； //素数添加结束后将最外层环出； } break； } iscut[k * i]=true； } } } return prime.size ()； //返回素数的个数)进行测试时，发现性能几乎没有差异。
5、缺点以此类推，直到最终序列中所有数字被标记：
二、欧拉筛(线性筛)欧拉筛对tldhk筛减少重复筛分，从而降低复杂度，达到o(n )。
1、原理欧拉筛和tldhk筛使用原理不同。 欧拉筛的次数=最小质因数*次数(质数)。 上述组合是唯一的。 欧拉筛不从素数序列出发，而是直接从数字序列开始依次扫描。 对于数组中的每个数字I，将I依次乘以素数数组的成员，得到num=i*prime[j]，然后筛选掉num，当num超过统计范围或i%prime[j]==0时退出循环2、代码实现intcountprimes(intn ) (vectorbooliscut ) n1 )； //筛选标记，真-被筛掉，假-向量图prime； //存储素数的容器for(intI=2； i=n； I ) if (！ iscut[I](/iscut[I]=false，即I不被筛掉，加上素数prime.push_back(i ) I； for(intj=0； j prime.size (； j () if ) I*prime[j]n ) /防止越境break； iscut[i * prime[j]]=true； //I质量加倍并滤去if (I % prime [ j ]==0)//*判断最小质因数，防止重复滤去break； } } return prime.size (； 返回//素数的个数注释：对整个欧拉筛的重要判断是i % prime[j]==0，如果为true，I可以被prime[j]整除，有k=i/prime[j]。 如果此时没有脱离循环，则下一个被筛选出的数为num=i*prime[j 1]，但num可以写为num=prime[j] * k * prime[j 1]。 也就是说，当i=k*prime[j 1]时，num还可以通过跳出被筛掉的循环来避免重复的筛除操作。
例： i=10时，素数排列有素数2、3、5、7。
不判断最小质因数时，被筛掉的数为20、30、50、70。 30在i=15的时候再筛一次。 因为30=15*2。
判断最小质因数时，被筛掉的数量为20个。 因为筛掉的数在20个后会因为10%2==0而跳出循环，30、50、70等会留在后面的数中被筛掉。 这样，可以有效避免重复被筛掉的操作。
总之，两种筛法使用的原理不同，tldhk筛法更直观，欧拉筛法需要理解。 两者的性能有差异，但实际上差别不大。