Eratosthenes筛选法与欧拉筛选法(整理)

大家好，欢迎来到IT知识分享网。

一、算法原理

一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。

二、步骤

（1）先把1删除（1既不是质数也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

…….

（n）读取队列中当前最小的状态为true的数n，然后把n的倍数删去

三、实现

问题：给一个数n，求出比n小的所有的质数有多少个

思路：用一个bool数组，存储n个数的状态，初始化都为true，然后从2开始，如果2的状态为true，就开始遍历比n小的所有的2的倍数，将其全部置为false。把2的倍数遍历完后，继续往下找下一个状态为true的数，即3，遍历比n小的所有的3的倍数（按3*3，3*4，3*5这样遍历，注意不需要从3*2开始了）。…..最后剩下的状态为true的数全为质数。

四、代码

 int countPrimes(int n) { vector<bool> vec_flag(n,true); vec_flag[0] = false; vec_flag[1] = false; for (int i = 2; i < sqrt(n);i++){ if(vec_flag[i]){ for(int j = i * i;j < n;j += i){ vec_flag[j] = false; } } } return count(vec_flag.begin(),vec_flag.end(),true); }

Eratosthenes筛选法虽然效率高，但是Eratosthenes筛选法做了许多无用功，一个数会被筛到好几次，最后的时间复杂度是O(nloglogn),对于普通素数算法而言已经非常高效了,但欧拉筛选法的时间复杂度仅仅为O(n).

欧拉算法是一种空间换时间的算法。

#include <iostream> using namespace std; const int MAXN = ; int prime[MAXN];//保存素数 bool vis[MAXN];//初始化 int Prime(int n) { int cnt = 0; memset(vis, 0, sizeof(vis)); //筛选与Eratosthenes不同，并不是按照顺序筛选，但每一个合数都等于一个数字乘以它的最小素因子，所以遍历每个数字 i 乘以小于i（若大于i，则i为最小素因子）的所有素因子可以保证，每个合数都被遍历到 for (int i = 2; i< n; i++) { if (!vis[i]) prime[cnt++] = i; for (int j = 0; j < cnt && i * prime[j] < n; j++) { cout <<"i:" << i << " prime[j]:" << prime[j] << " i*prime[j] : "<< i*prime[j] << endl; vis[i*prime[j]] = 1; if (i%prime[j] == 0)//关键 每一个筛选数，只被一个数乘以它的最小素因子，如果i % prime[j] == 0，则证明 i中含有prime[j]这个素因子，所以prime[j + 1] 至 prime[prime.size()-1]都不是最小素因子 break; } } return cnt;//返回小于n的素数的个数 }

参考地址：

http://blog.csdn.net/xiaoquantouer/article/details/

http://www.bubuko.com/infodetail-837565.html