Eratosthenes筛法名字虽然高贵冷艳，但是并不难理解，原理就不多说了，但是它做了许多无用功，一个数会被筛到好几次，最后的时间复杂度是O（nloglogn），不要以为这个复杂度已经很好了，因为有直接O（n）的欧拉筛法存在，下面简单叙述一下其原理，最后由程序的运行结果来说明两者的差距。
欧拉筛法的思想就是不做无用功，原本Eratosthenes筛法的第一重循环是用来找素数，然后把素数的倍数标记，而欧拉筛法换了一个角度，第一位是找素数没有问题，但是标记的时候用的是所有数（合数素数都能用来做标记）来标记，并加上了一句特判来跳出循环，什么意思呢？对于当前的一个数i，欧拉筛法把从2，， 3， 5….到小于 i 的最大素数分别和 i 相乘得到的数标记成合数。并且过程中一旦发现 i % （p[j]） == 0，则跳出循环，有什么用呢？这样做保证了每个合数只被他的最小素因子筛到一次，为什么？这么想，我们每次想要标记的数是 i * p[j]， 有因子p[j], 如果 i 没有因子 p[j] 则标记（这是第一次用p[j]标记的时候干的事）,易于发现当 i 中 p[j] 的指数为x时，i 是被 (i / p[j]) 这个数 * p[j] 时标记的，只标记了一次。
下面是两者对比的代码，网上看到说由于欧拉筛法的特判有取模运算，所以在数据小的时候不如Eratosthenes筛法快，亲测了一下，根本感觉不到差距，反而是数据变大以后，两者差距变得越来越明显，从消耗的时间上可以看出。（当然我在其中加了求欧拉函数的操作）。欧拉筛法的思想很巧妙，特别是应用在求一些积性函数的时候会比普通筛法更快，比如欧拉函数。
#include<cstring>#include<iostream>#include<ctime>using namespace std;#define N 100000005bool vis[N];int p[N], cnt, phi[N];int Euler(int n){int i, j, k;phi[1] = 1;for (i = 2; i < n; ++i){if (!vis[i]){p[cnt++] = i;phi[i] = i – 1;}for (j = 0; j < cnt && i * p[j] < n; ++j){vis[i * p[j]] = true;if (i % p[j]) phi[i * p[j]] = phi[i] * phi[p[j]];else {phi[i * p[j]] = phi[i] * p[j];break;}}}return cnt;}int Eratosthenes (int n){int i, j, k;phi[1] = 1;for (i = 2; i < n; ++i){if (!vis[i]) p[cnt++] = i;for (j = i; j < n; j += i) {if (!phi[j]) phi[j] = j;phi[j] = phi[j] / i * (i – 1);vis[j] = true;}}return cnt;}int main(){clock_t st, en;int num;double sec;for (int t = 10; t < N; t *= 10){cout << t << ‘:’ << endl;st = clock();num = Euler(t);en = clock();sec = (double)(en – st) / (double) CLOCKS_PER_SEC;//cout << "Euler : " << cnt << ‘ ‘ << sec << endl;printf("Euler :\t\t%8d\t%.8lf\n", num, sec);memset(vis, 0, sizeof(vis)), memset(p, 0, sizeof(p)), memset(phi, 0, sizeof(phi)), cnt = 0;st = clock();num = Eratosthenes(t);en = clock();sec = (double)(en – st) / (double) CLOCKS_PER_SEC;//cout << "Eratosthenes : " << cnt << ‘ ‘ << sec << endl;printf("Eratosthenes :\t%8d\t%.8lf\n", num, sec);}return 0;}
两张图片，后一张是没有加求欧拉函数操作的运行结果，所以以后应该不会再用Eratosthenes筛法了。。。。
分明是比谁记的都清楚，比谁都更加在意，
