欧拉筛

欧拉筛是线性时间复杂度筛选素数的算法。

先看一般筛法寻找素数：

findPrime(n)
    isPrime = array
    primes = empty-list
    isPrime[] = false;
    for(i = ; i < n; i++)
        isPrime[i] = true
    for(i = ; i < n; i++)
        if(isPrime[i])
            primes.add(i)
        for p in primes<br />　　　　　　  if(p * i >= n) break
            isPrime[i * p] = false<br />　　return primes

先说明上面的代码可以正确找到所有[1,n)之间的素数。如果一个数x是素数，那么isPrime[x]恒为真。如果x为合数，则可以分解为p与x/p，其中p是x的最小素因子。而p,x/p<x，我们不妨设p<=x/p，则当i=x/p时，此时p已经作为素数加入到了primes中，而isPrime[p * i] = false会将x设为合数，因此x会作为合数分离出去。故最后所有的素数都记录在了primes中，且记录在primes中的也只有素数。

上面的过程是正确的，时间复杂度为∑ln(i)=O(ln(n)*n)。ln(n)是素数定理中对素数分布的估计。

我们发现上面这个过程中涉及到多次对同一个合数设置其isPrime属性，比如12，会由于4*3以及6*2被两次设置，而由于多次设置的现象存在，我们很难将时间复杂度优化到线性。而欧拉筛则在上面这个素数筛的基础上，要求只有当i取值为x的最大因子时，才允许设置x为合数。而实现出乎意料的简单，只用加上一行代码。

<span>findPrime(limit)
   isPrime =<span> array
   primes = empty-<span>list
   isPrime[1] = false<span>;
   for(i = 2; i < limit; i++<span>)
       isPrime[i] = true
   for(i = 2; i < limit; i++<span>)
       if<span>(isPrime[i])
           primes.add(i)
       for p in<span> primes<br />　　　　　　 if(i * p >= n) break　
           isPrime[i * p] = false<br />　　　　　　 if(i % p == 0) break<br />　　return primes

先说明这个算法是正确的。当i>p且能整除p时，对于任意素数k>p，ik的最大因子显然不是i（至少为pk），因此可以直接跳过后面的流程。当然还有一种特殊情况就是i=p，此时跳出与不跳出都不影响结果，因为循环已经濒临结束了。而对于primes中最终结果的正确性与上面算法的证明一致。

对于时间复杂度，外部循环最多执行n次，每次都是常数时间复杂度，而内部循环每次执行都会设置一个合数的isPrime属性，而每个合数只会被设置一次，因此内部循环执行的次数与合数总数等阶，即为O(n)。因此总的时间复杂度为O(n)。