质数筛法:埃氏筛和欧拉筛

质数数筛法

本文主要介绍埃氏筛法和欧拉筛法。

判断单个数是不是质数

bool isPrime(int num)
{
	if(num == 1)
		return 0;
	if(num==2 || num==3)
		return 1;
	if(num%6 != 1 && num%6 != 5)
		return 0;
	int tmp = sqrt(num);
	for(int i=5; i <= tmp; i+=6)
		if(num%i==0 || num%(i+2) == 0)
			return 0;
	return 1;
}

但是当有很多个数需要判断的时候，每次都输入num判断是否是质数就很耗时了，这样提前将一个范围的质数算出来可以更节省时间，所以就用到了质数筛法。

暴力筛法

学习埃氏筛之前，我们先看一下暴力筛法，即对每个数都用试除法判断其是不是质数：

static constexpr int N = 1e7 + 5;
int st[N]; // 初始化为0， 0表示质数，1表示合数

for(int i = 2; i <= n; i++){
	for(int j = 2; j <= i / j; j++){//试除法
		if(i % j == 0){
			st[i] = 1; // 合数，标记为1 
		}
	}
}

埃式筛

暴力筛法无疑是最慢的，我们看一下如何加快，换一种思路：一个质数的倍数一定是合数，所以，假设\(P\)是质数，我们可以筛掉区间\([1,1e7]\)中所有\(P\)的倍数。 先看个例子，对于数列1~11：

先筛去2的倍数：

再筛去3倍数：

再筛去5倍数：

至此，1~11内的所有合数都被筛完了， 2 3 5 7 11是数列中的质数。

为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。

埃氏筛代码：

static final int N = 1e7 + 5;
static int[] st = new int[N];
public static void E_sieve(int  n)
{

	for(int i = 2; i <= n; i++)
	{
		if(st[i] == 0)
		{
			for(int j = 2 * i; j <= n; j += i)
			    st[j] = 1;  // j是i的一个倍数，j是合数，筛掉。
		}
	}
	
}

以上代码的时间复杂度为\(O(n\log{\log_2 n} )\)

我们还可以对其进行优化：

• 我们会先筛\(2\)的所有倍数，然后筛\(3\)的所有倍数，但筛除\(3\)的倍数时，我们还是从\(3\)的\(2\)倍开始筛，其实\(3 * 2\) ，已经被\(2 * 3\)时筛过了。 又比如说筛5的倍数时，我们从5的2倍开始筛，但是\(5 * 2\)会先被\(2 * 5\)筛去， \(5 * 3\)会先被\(3 * 5\)会筛去，\(5 * 4\)会先被\(2 * 10\)筛去，所以我们每一次只需要从\(i*i\)开始筛，因为\((2，3,…,i - 1)\)倍已经被筛过了。
• 另外，判断一个数 \(n\)是不是质数，我们只判断\([2, \sqrt{n} ]\)内有没有它的因子。在筛合数的时候，我们也可以这样做，因为一个合数的最小质因子一定小于等于 \(\sqrt{n}\)。所以对于区间\([1, 1e7]\)，最大的合数是 \(1e7\), 它的最小质因子一定是小于等于 \(\sqrt{1e7}\) ，区间内其他的合数的最小质因子也一定是小于等于 \(\sqrt{1e7}\)的，所以只需要用\([1, \sqrt{1e7}]\)中的质数就可以筛去 \([1, 1e7]\)中所有的合数。

优化后的埃式筛：

static final int N = 1e7 + 5;
static int[] st = new int[N];
public static void E_sieve(int  n)
{
    // 注意循环条件i <= n / i，为什么不直接成sqrt(n)?
    // 写成这样的形式当i >= sqrt(n) 时候依然可以停止循环，而且加减法需要几个时钟周期，乘法需要10几个时钟周期，除法需要2、3十个时钟周期，开根号需要8000个时钟周期，这样可以节省时间
	for(int i = 2; i <= n / i; i++)
	{
		if(st[i] == 0)
		{
			for(int j = i * i; j <= n; j += i)
			    st[j] = 1;  // j是i的一个倍数，j是合数，筛掉。
		}
	}
	
}

优化后的时间复杂度可以近似看成\(O(n)\)了。

欧拉筛

优化后的埃式筛时间复杂度可以近似看成\(O(n)\)，但是欧拉筛可以比它更快，欧拉筛的时间复杂度是\(O(n)\)，又被称为线性筛。

埃氏筛是筛去每个质数的倍数，但难免，会有合数会被其不同的质因子多次重复筛去。这就造成了时间浪费。

比如说： \(120 = 2^3 * 3 * 5\),\(120\) 会被\(2\)筛去一次， \(3\)筛去一次， \(5\)筛去一次。 多做了两次不必要的操作。

那么我们如何确保120只被2筛掉呢？在埃氏筛中我们用了一个循环来筛除一个质数的所有倍数，即对于p来说，筛除数列： \(2 * p , 3 * p, ... , k*p\)。另外，我们是从小到大枚举区间中的每个数的，数列是：\(2,3,4,...,n\)。

对比两个数列：

\[\begin{align} &2 * p , 3 * p, ... , k*p \\ &2,3,4,...,n \end{align}\]

会发现，第二个数列是第一个数列的系数,所以，我们不需要用一个for循环去筛除一个质数的所有倍数，我们将所有质数存储到primes[]中，然后枚举到第i个数时，就筛去所有的primes[j] * i。这样就在每一次遍历中，正好筛除了所有已知素数的i倍。

代码如下：

static constexpr int N = 1e7 + 5;
//isPrime[i] == 1表示：i是素数
vector<bool> isPrime;
//Prime存质数
vector<int> Prime;
int cnt = 0;
void GetPrime(int n)//筛到n
{
    Prime.push_back(0);
    isPrime.resize(N, 1);
    //以“每个数都是素数”为初始状态，逐个删去
    isPrime[1] = 0;//1不是素数

    for(int i = 2; i <= n; i++)
    {
        if(isPrime[i])//没筛掉 
        {
            Prime.push_back(i);
            ++cnt;
        }
            

        for(int j = 1; j <= cnt && i * Prime[j] <= n/*不超上限*/; j++) 
        {
            //从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
            isPrime[i * Prime[j]] = 0;

            if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
                break; //重要步骤。见原理
        }
}
}

注意内层循环有一个break的条件i % primes[j] == 0,为什么呢？

因为:

由

\[i \quad \% \quad primes[j] == 0\]

可得

\[primes[j] * k = i \tag{1}\]

设

\[primes[j] * k = X\tag{2}\]

将\((1)\)代入到\((2)\)中可得

\[primes[j+1] * primes[j] * k = X\]

因为\(primes[j+1] > primes[j]\),所以\(primes[j+1] * k > i\)。

设

\[primes[j] * k = i^\prime\]

则

\[primes[j] * i^\prime = X\tag{3}\]

所以如果用\((2)\)式筛去\(X\)的话，当\(i\)等于\(i'\)时，\(X\)又会被\((3)\)式筛去一次，为了确保合数只被最小质因子筛掉，最小质因子要乘以最大的倍数，即要乘以最大的\(i\), 所以不能提前筛。

比如说 \(1 ，2，3，4，5，6，7，8，9，10，11， 12\),当i == 4 时, primes = {2, 3},此时 i % 2 == 0, 如果不结束内层循环的话， \(12\)会被\(3*4\)筛掉， 当i == 6时，\(12\)又会被\(2*6\)筛掉。

欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。