Lc 204 经典题目-计算质数个数

zyleo

2020-12-03 约 1068 字预计阅读 3 分钟

经典数学题，计算小于n的质数的个数

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10

输出：4

解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

数据范围： 0 <= n <= 5 * 106

一看今天的每日一题，难度简单，我心想这不是10分钟就把它给冲了？看完之后才发现，它说它是简单题，它可不是简单题啊，它这是有备而来，它明明就是一道数学题。

基础解法

最简单的想法当然是遍历从2开始的所有小于n的数，然后判断是否为质数，这样的话复杂度将会是$O(n \sqrt{n})$，意料之内，会超时，所以这种方法不行。

进阶

埃氏筛选

这种方法由希腊数学家厄拉多塞（Eratosthenes）提出，思路是遍历到一个质数$x$后，将其倍数$2\times x$、$3\times x$、$4\times x$…都标记为合数，这样利用了数与数之间的关联性，减少了很多没必要的判断质数操作。进一步优化其时间复杂度，可以发现，不用从$2\times x$开始，因为这样会对一个合数进行多次重复标记（比如$15 = 3\times 5$），在计算3时会乘以5，而计算5时又会乘以3。所以可以从$x\times x$开始标记。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def countPrimes(self, n: int) -> int:
        '''
        埃氏筛选法
        '''
        isPrime = [True for i in range(n)]
        res = 0
        for j in range(2, n):
            if isPrime[j]:
                res += 1
                print(j)
                tmp = j * j
                while tmp < n:
                    isPrime[tmp] = False
                    tmp += j
        
        return res

线性筛选

在埃氏筛选的基础上，还是会有重复的标记合数操作，比如30在遍历到3的时候，会被标记为合数($3\times 3 < 30$)，遍历到5的时候，又会被标记为合数。所以还需要对这个方法进行优化。前人已经想出的思路是空间换时间，在遍历的时候使用一个数组存储所遇见的质数，数组为[$P_0, P_1, …, P_i, …$]，并且对每个数$x$，将$x\times P_i$标记为合数，并且到$x\equiv 0 \pmod {P_i}$时结束。

因为假如$x \equiv 0 \pmod {P_i}$，然后再往后标记，即将$x \times P_{i+1}$标记为合数，那么因为$\frac{x}{P_i} \times P_{i+1} > x$，所以在后面遍历到$\frac{x}{P_i} \times P_{i+1}$这个数时，将其乘以$P_{i}$就会把$x \times P_{i+1}$标记为合数，与之前的操作重复，所以我们应该把到此停止，把$x \times P_{i+1}$这个数留给后面的大于$x$的数去标记。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countPrimes(self, n: int) -> int:
        '''
        线性筛选法
        '''
        primes = []
        isPrime = [True for i in range(n)]
        for i in range(2, n):
            if isPrime[i]:
                primes.append(i)
            j = 0
            while j < len(primes) and i * primes[j] < n:
                isPrime[i * primes[j]] = False
                if i % primes[j] == 0:
                    break                
                j += 1
        # print(primes)
        return len(primes)

时间复杂度： $O(n)$，这一点是让我感觉比较出乎意料的，看来自己还是太菜了 :-(。

目录

Lc 204 经典题目-计算质数个数

基础解法

进阶

埃氏筛选

线性筛选