4、改进后代码

int countPrimes(int n) {vector<bool>iscut(n+1);             //筛选标记，true-被筛掉，false-未筛除vector<int>prime;                   //存储素数的容器for (int i = 2; i < n+1; i++){   if (!iscut[i]) {                //iscut[i]=false,即i未被筛掉，加入素数prime.push_back(i);for (int k = i; k < n; k++){//把i的倍数筛掉if (k * i > n){         //防止越界if (k == i){        //是i的平方越界，直接把序列中剩余数加入到素数for (int j = i+1; j <= n; j++){if(!iscut[j])prime.push_back(j);}i = n + 1;      //添加素数完毕后将最外层循环跳出;}break;}iscut[k * i] = true;}}}return prime.size();             //返回素数个数
}

改了之后测试发现性能几乎没有区别。。。。

5、缺点

会有一些数被重复地筛除掉，造成了不必要的计算量。例如数字16，被2*8和4*4筛除。

二、欧拉筛(线性筛)

欧拉筛相对埃氏筛而言就是减少了重复的筛除，从而降低复杂度，达到O(n)。

1、原理

1. 欧拉筛与埃氏筛使用的原理有所区别。欧拉筛是合数=最小质因数*合数(质数)。以上组合唯一。
2. 欧拉筛中不是从素数序列中出发，而是直接从数字序列依次遍历。对序列中的每一个数字i，将i依次与素数序列成员相乘得到num=i*prime[j]，然后将num筛除掉，当num超出统计范围或者i%prime[j]==0(原因后面会讲)时退出循环。

2、代码实现

int countPrimes(int n) {vector<bool>iscut(n + 1);             //筛选标记，true-被筛掉，false-未筛除vector<int>prime;                     //存储素数的容器for (int i = 2; i <= n; i++){if (!iscut[i])                    //iscut[i]=false,即i未被筛掉，加入素数prime.push_back(i);for (int j = 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等就留到后面的数进行筛除，这样就有效避免了重复筛选除的操作。

总结

总的来说，两种筛法使用的原理有所不同，埃氏筛法更为直观，欧拉筛则需要理解一下。两者的性能虽然有所区别，但实际上区别并不大。

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