Created by 高松 on 16/4/17

Copyright © 2016年 Yisa. All rights reserved.

概述：

当我们谈论到质数筛选时,一个最初的想法是在遍历1~N中的每个数字，判断一下是否质数，这种最简单的方法虽然代码十分容易写，但是效率极低。事实上，在筛选质数上早已有了古老的Eratosthenes筛法，本文将重点探讨Eratosthenes筛法与Eular筛法两种方法。

Eratosthenes筛法

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数.Eratosthenes筛法的算法思想十分简洁明了，用伪代码的表达方式如下:

isPrime [] = true
primeCount = 0;
For i = 2 .. N
    If isPrime[i] Then
        primeCount = primeCount + 1
        multiple = 2
        While (i*multiple ≤ N)
            isPrime [i * multiple] = false
            multiple = multiple +1
        End While
    End If
End For

<br>

　　这样的方法就是古老的Eratosthenes筛法，值得注意的是，这个方法的时间复杂度为
O(n log log n)，必须承认的是，Eratosthenes筛法有他本身的冗余度，当我们对于某个合数k进行计算时，我们会不止用到一次他的质因数。

　　以合数10为例，当我们以质数2将isPrime[10]标记为false时，当我们循环走到i=5时，依旧会循环遍历到isPrime[10]，这就造成了冗余。事实上，若是采用Eular筛法，我们可以将时间复杂度降为O(n).

Eular筛法

我们可以知道，任意一个正整数k，若k≥2，则k可以表示成若干个质数相乘的形式。Eratosthenes筛法中，在枚举k的每一个质因子时，我们都计算了一次k，从而造成了冗余。因此在改进算法中，只利用k的最小质因子去计算一次k。

首先让我们先了解一下Eular筛法，伪代码如下：

 isPrime [] = ture
 primeList [] 
 primeCount = 0
 For i = 2 .. N
    If isPrime[i] Then
        primeCount = primeCount + 1
        primeList[ primeCount ] = i
    End If 
For j = 1 .. primeCount
    If (i * primeList[j] > N) Then
        Break
    End If
    isPrime[ i * primeList[j] ] = false
        If (i % primeList[j] == 0) Then
            Break
        End If
    End FOr
End For

与Eratosthenes筛法不同的是，对于外层枚举i，无论i是质数，还是是合数，我们都会用i的倍数去筛。但在枚举的时候，我们只枚举i的质数倍。比如2i,3i,5i,…，而不去枚举4i,6i…，原因我们后面会讲到.

假设一个合数k=M*p1，p1为其最小的质因子。则k只会在i=M，primeList[j]=p1时被筛掉一次。首先会在i=M，primeList[j]=p1时被筛掉是显然的。

其次不会在其他时候被筛掉。否则假设k在i=N, primeList[j]=p1时被筛掉了，此时有k=N*p2。由于p1是k最小的质因子，所以p2 > p1，M > N且p|N。则i=N，j枚举到primeList[j]=p1时(没到primeList[j]=p2)就break了。所以不会有其他时候筛掉k。

同时，不枚举合数倍数的原因也在此：对于一个合数k=M 2 3 。只有在枚举到i=M 3时，才会计算到k。若我们枚举合数倍数，则可能会在i=M时，通过M 6计算到k，这样也就造成了多次重复计算了。

综上，Eular筛法可以保证每个合数只会被枚举到一次，时间复杂度为O(n)。当N越大时，其相对于Eratosthenes筛法的优势也就越明显。