解决素数筛选问题的几个算法。以该问题为例:求出小于非负整数 n 的素数的数量。

解法一 枚举

用到一个数学结论:对于一个正整数X,以它的平方根\sqrt{X}为界,两边的因子是一一对应的。即判断一个数是否为素数,仅需判断它是否能整除 [2, \sqrt{X}] 中的某个正整数,如果能则不是素数,反之为素数。C#代码如下:

public class Solution {
    public bool IsPrime(int x)
    {
        for(int i = 2; i * i <= x; i++)
        {
            if(x % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    public int CountPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++)
        {
            if(IsPrime(i)) count++;
        }
        return count;
    }
}

该算法的时间复杂度为 O(n\sqrt{n})

对于所有的素数筛法,都可以用奇偶性去优化。因为素数一定是奇数,除2以外的偶数一定不是素数,那么上面的代码可以优化为:

public class Solution {
    public bool IsPrime(int x)
    {
        for(int i = 2; i * i <= x; i++)
        {
            if(x % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    public int CountPrimes(int n) {
        int count = n > 2 ? 1 : 0;
        for(int i = 3; i < n; i += 2)
        {
            if(IsPrime(i)) count++;
        }
        return count;
    }
}

 

解法二 埃氏筛

埃氏筛所用到的数学结论是:对于每个质数,其整数倍总是合数,并且只要遍历所有质数的整数倍,一定能找到所有合数。

所以要找到 [2, n) 中素数的数量,只需要从2开始遍历,遇到质数  P 时计数加一,并且将 \{ S | S = k*P, 2 \le S < n, k = 2, 3, ... \} 中所有数标记为合数。不难看出:一个数若是合数,必定在遍历到这个数之前就会被标记为合数,如果遍历到某个数时,它没有被标记为合数,那么它一定是素数。C#代码如下:

public class Solution {
    public int CountPrimes(int n) {
        //flag 是否标记为合数
        bool[] flag = new bool[n];
        int count = 0;
        for(long i = 2; i < n; i++)
        {
            if(!flag[i])
            {
                count++;
                for(long j = 2 * i; j < n; j += i) flag[j] = true;
            }
        }
        return count;
    }
}

上面的埃氏筛算法是可以进一步优化的,因为很多数被重复标记了,例如 10 会被 2 和 5 标记,为了减少重复标记,我们可以改变代码中 j 的起始数。首先,不难看出对于每一次循环,j 总是按这些数遍历:2i, 3i, 4i, ..., k * i, ... , [\frac{n}{i}] * i 且如果 k < i ,那么 k * i 一定在遍历 k 这个数时就已经被标记了,所以我们只需要让 j 从 i * i 开始标记即可。

不过这种优化并不能完全消除重复标记,比如 12 依旧会被 2 和 3 标记。

再加上奇偶性优化后新的代码如下:

public class Solution {
    public int CountPrimes(int n) {
        //flag 是否标记为合数
        bool[] flag = new bool[n];
        int count = n > 2 ? 1 : 0;
        for(long i = 3; i < n; i += 2)
        {
            if(!flag[i])
            {
                count++;
                for(long j = i * i; j < n; j += i) flag[j] = true; 
            }
        }
        return count;
    }
}

埃氏筛的时间复杂度是 O(nloglogn),证明略。

解法三 线性筛

埃氏筛的重复标记能不能完全消除呢?答案是可以的。埃氏筛重复的原因在于,它是通过(质数P * 大于P的数)来标记所有的合数的,但对一个合数的(质数P * 大于P的数)形式分解不是唯一的,例如 12 = 2 * 6 = 3 * 4

要想完全消除重复,我们还是要回到算术基本定理,即对于任何正整数X,都可以唯一表示成质数的乘积,例如 12 = 2 * 2 * 3。换句话说,两个或两个以上的质数乘积,唯一确定一个合数。若是两个合数分解后的质因子不完全相同,那么这两个合数一定不相等。

为了枚举所有的质因子组合并且不重复,我们需要将质数记录下来,即遍历时遇到质数,就将其存在质数表中。在枚举过程中,我们不再是遇到质数时标记其整数倍,而是对于任何数 X ,我们将 X 依次乘以当前质数表中的所有质数,所得到的那些数一定是合数。这样筛出的合数会不会重复呢?答案是依旧会。

例如当遍历到 X = 4 时,这个时候质数表为 [2, 3],可以标记合数 [8, 12]

当遍历到 X = 6 时,这个时候质数表为 [2, 3, 5],可以标记合数 [12, 18, 30]

可以看出 12 被重复标记了,这是因为当 X 与 质数 P 相乘时,若 X \% P = 0 则对于 X 与 大于P的质数 S 的乘积 X * S,一定会在后面遍历到 \frac{X}{P} * S 这个数时被再次标记(通过该数乘以P)。

所以,我们需要在乘以质数表的时候,加上一个终止条件,若当前数以该质数作为一个因子,那么后面的质数就不用乘了。

例如当遍历到 X = 4 时,这个时候质数表为 [2, 3],标记合数 [8],因为 4 \% 2 = 0,所以 2 后面的所有质数就不用乘了。

同理,当遍历到 X = 6 时,这个时候质数表为 [2, 3, 5],可以标记合数 [12]

这样筛出的合数还会重复吗?答案是一定不会。因为此时可以保证与 X 相乘的质数 P,一定是所标记合数(即 X * P)的最小质因子。这就保证了每个合数,只会被其最小质因子所标记,那么一定不会重复。即每个数只会被标记一次,时间复杂度为O(n)

C#实现代码如下:

public class Solution {
    public int CountPrimes(int n) {
        //flag 是否标记为合数
        bool[] flag = new bool[n];
        List<long> primes = new List<long>();
        for(long i = 2; i < n; i++)
        {
           if(!flag[i]) primes.Add(i);
            foreach(long p in primes)
            {
                if(i * p >= n) break;
                flag[i * p] = true;
                if(i % p == 0) break;
            }
        }
        return primes.Count;
    }
}