质数计数问题求解

题目

leetcdoe204 计数质数：https://leetcode.cn/problems/count-primes

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例1：

• 输入：n = 10

• 输出：4

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

示例 2：

• 输入：n = 0

• 输出：0

示例 3：

• 输入：n = 1

• 输出：0

暴力解

直接判断小于 <n 中每个数是否为质数，是的话统计个数 +1，实现方法略过。

由于判断数字是否为质数时间复杂度为 $O(\sqrt{n})$，所以整体时间复杂度$O(n\sqrt{n})$，直接超时。

Temp

埃氏筛

参考 leetcode 官方题解：https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/

解题思路

枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

我们考虑这样一个事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,4x,… 一定不是质数，因此我们可以从这里入手。

我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即0，这样在运行结束的时候我们即能知道质数的个数。

这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 isPrime[x] = 0 。因此，这种方法也不会将合数标记为质数。

当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x*x 开始标记，因为 2x,3x,4x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。

举个例子：

假设需要判断 n=17 的埃氏筛：

x=2，需要划掉 >= 2^2 的2的倍数，即 4,6,8,10,12,14,16

x=3，需要划掉 >= 3^2 的3 的倍数，即 9,12,15（12已经被2划掉过，这里产生了冗余过程）

x=4，之前已经被2划掉了，说明是合数，跳过

x=5，需要划掉 >= 5^2 的5 的倍数，但是 5^2 = 25 > 17，什么也不用干

后面的也类似，要么已经被划掉了，要么 x^2 > 17。

因此最后，留下了 2,3,5,7,11,13,17

复杂度

• 时间复杂度：O(nloglogn)，这里就不严格证明了。

• 空间复杂度：O(n)。我们需要 O(n) 的空间记录每个数是否为质数。

实现代码

标准实现：

    def countPrimes(n: int) -> int:
        if n == 0 or n == 1:
            return 0
        prime_arr = [True] * n
        prime_arr[0] = False
        prime_arr[1] = False
        cur = 2
        while cur * cur <= n:
            if prime_arr[cur]:
                num = cur * cur
                while num < n:
                    prime_arr[num] = False
                    num += cur
            cur += 1
        result = 0
        for is_prime in prime_arr:
            if is_prime:
                result += 1
        return result

由于除了 2 以外的所有偶数都不是质数，那么我们可以对这一部分数据进行剪枝处理

    def countPrimes(n: int) -> int:
        if n < 3:
            return 0
        # f如果j确定是合数, 将 f[j] 设置为 True
        f = [False] * n
        # 所有偶数都不要, 剩余的个数
        count = n // 2
        cur = 3
        while cur * cur < n:
            if not f[cur]:
                # cur 的 倍数中小于 cur * cur 的已经由其他数添加了
                # cur 只用考虑奇数
                for j in range(cur * cur, n, 2 * cur):
                    if not f[j]:
                        count -= 1
                        f[j] = True
            cur += 2
        return count

埃氏筛拓展

Euler Project 10

先看一道类似的题目：求出 200万 以内所有质数之和

参考自：https://www.zhihu.com/question/29580448/answer/45218281

这个算法原题来自 https://projecteuler.net/problem=10

在论坛中由 Lucy_Hedgehog 给出具体计算流程。

整体思路

这里以Euler Project 10 中的解，说明计算过程。（即求质数和，而不是质数个数）。

定义 $S(v,p)$ 为2…v 所有整数中，在上面的埃氏筛中，外层循环筛完p 时，仍然幸存的数的和。

因此这些数：

• 要不本身是素数

• 要不其最小的素因子也大于p

因此我们需要求的是：$S(n,\lfloor \sqrt{n}\rfloor )$，n=200w

为了计算$S(v,p)$，先考虑几个特殊情况

1）$p\le 1$时所有数都还没有被筛掉，所以 $S(v,p)={\sum }_{i=2}^{v}i=\frac{(2+v)(v-1)}{2}$

2）p 不是素数。因为筛法中早已被别的数筛掉，所以在这步什么都不会做，所以此时 $S(v,p)=S(v,p-1)$

3）p是素数，但是 $v<p^2$。因为每个合数都一定有一个不超过其平方根的素因子，如果筛到 p时还没筛掉一个数，那么筛到 p−1 时这个数也还在。所以此时也有$S(v,p)=S(v,p-1)$

举个例子

如果 v = 30，p=7，埃氏法中以 7 开头筛选的数字中，最小的为 7 * 7 = 49 > 30，不会划掉任何数字
因此此时和外层筛选到 6 相比，没有做任何操作。

现在考虑最后一种稍微麻烦些的情况：p 是素数，且 $p^2\le v$。

此时，我们要用素数 p 去筛掉剩下的那些数中 p 的倍数。注意到现在还剩下的合数都没有小于 p 的素因子。因此有：

$S(v,p)=S(v,p-1)-\sum k，其中，2\le k\le v，且k最小素因子为p$

后面那项中提取公共因子 p，有：

$S(v,p)=S(v,p-1)-p\times \sum \frac{k}{p}，其中，2\le k\le v，且k最小素因子为p$

因为 p 整除 k，稍微变形一下，令 t &#