一般来说，我们求素数都会用的两种最基本简单的方法就是埃氏筛法和欧拉筛法了。你真的了解什么是埃氏筛法，什么是欧拉筛法吗?你知道他们两者之间的区别是什么吗?下面，就让我们来给大家详细说说吧。

欧拉筛法

　　埃氏筛法eratosthenes筛法(sieve of eratosthenes)由于思想非常简单，故只给出实现。

　　欧拉筛法是一种线性算法，并且同时可以计算出每个数的φφ。

　　做法:回顾经典的eratosthenes筛法，它可能对同一个质数筛去多次。那么如果用某种方法使得每个合数只被筛去一次就变成是线性的了。不妨规定每个合数只用其最小的一个质因数去筛，这便是欧拉筛法了。

　　简单证明:这个看似很简单，其实还是要注意一下细节的。搞清了证明其他的问题也就清楚了。证明分两部分。首先证每个合数都会被筛到(正确性)，其次证每个合数只会被筛到一次(复杂度)。

　　每个合数都会被筛到，设有一合数n=pk11...pkmmn=p1k1...pmkm(pipi为质数)，则nn一定会在i=pk1−11...pkmmi=p1k1−1...pmkm时被筛去(此时primes[j]=p1primes[j]=p1)，因为对于小于p1p1的质数，一定不会被ii整除。每个合数都只会被筛到一次。与上面一样，还是设有一合数n=pk11...pkmmn=p1k1...pmkm(pipi为质数)。倘若存在一个质因子px(x≠1)px(x≠1)也筛去了nn，那么此时i=pk11...pki−1x...pkmmi=p1k1...pxki−1...pmkm。i>pxi>px，此时在内层循环中已经早早地break掉了，因为p1∣ip1∣i。i可能在x=mx=m时发生)。

欧拉筛法

　　难以理解的地方

　　i % primes[j] == 0为何不放在前面?你可以去试试……实践出真知。放前面的话，所有的“某个质因子的次数不为1”的合数便会被当成质数。至于为什么，请看证明。实践才是检验真理的唯一标准。

　　当ii为质数时，内层循环会在最后一个质数(也就是ii自己)终止。当ii为合数时，内层循环会在它的第一个质因数终止。当然加了也没有问题。顺便把φφ算出来?其实这是极简单的。主要基于以下事实：(很容易通过定义推出来，不妨自己试试)

　　1.n为质数时，phi(n) = n - 1

　　2.p为质数且p整除n时，phi(n*p) = p* phi(n)

　　3.p为质数且p不整除n时，phi(n*p) =(p - 1) * phi(n)

　　由此可见，埃氏筛法和欧拉筛法的区别差距还是蛮大的呢。eratosthenes筛法名字虽然高贵冷艳，但是并不难理解，原理就不多说了，但是它做了许多无用功，一个数会被筛到好几次，最后的时间复杂度是o(nloglogn)，不要以为这个复杂度已经很好了，因为有直接o(n)的欧拉筛法存在。欧拉筛法的思想就是不做无用功。