【算法】素数筛法

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

解法一 枚举

用到一个数学结论：对于一个正整数，以它的平方根为界，两边的因子是一一对应的。即判断一个数是否为素数，仅需判断它是否能整除 中的某个正整数，如果能则不是素数，反之为素数。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;
    }
}

该算法的时间复杂度为

对于所有的素数筛法，都可以用奇偶性去优化。因为素数一定是奇数，除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开始遍历，遇到质数  时计数加一，并且将 中所有数标记为合数。不难看出：一个数若是合数，必定在遍历到这个数之前就会被标记为合数，如果遍历到某个数时，它没有被标记为合数，那么它一定是素数。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 总是按这些数遍历： 且如果 ，那么 一定在遍历 k 这个数时就已经被标记了，所以我们只需要让 j 从 开始标记即可。

不过这种优化并不能完全消除重复标记，比如 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;
    }
}

埃氏筛的时间复杂度是 ，证明略。

解法三 线性筛

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

要想完全消除重复，我们还是要回到算术基本定理，即对于任何正整数，都可以唯一表示成质数的乘积，例如 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的质数 S 的乘积 ，一定会在后面遍历到 这个数时被再次标记（通过该数乘以P）。

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

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

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

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

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;
    }
}