质数计数问题求解

本文主要是介绍质数计数问题求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

质数计数问题求解

题目

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})$，直接超时。

埃氏筛

参考 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,16x=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)$ 的空间记录每个数是否为质数。

实现代码

标准实现：

• Python实现

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

• Java实现

public int countPrimes(int n) {int[] isPrime = new int[n];Arrays.fill(isPrime, 1);int ans = 0;for (int i = 2; i < n; ++i) {if (isPrime[i] == 1) {ans += 1;if ((long) i * i < n) {for (int j = i * i; j < n; j += i) {isPrime[j] = 0;}}}}return ans;
}

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

• Python实现

    def countPrimes(n: int) -> int:if n < 3:return 0# f如果j确定是合数, 将 f[j] 设置为 Truef = [False] * n# 所有偶数都不要, 剩余的个数count = n // 2cur = 3while 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 -= 1f[j] = Truecur += 2return count

• Java实现

public int countPrimes(int n) {if (n < 3) {return 0;}boolean[] f = new boolean[n];int count = n / 2;for (int i = 3; i * i < n; i += 2) {if (f[i]) {continue;}for (int j = i * i; j < n; j += 2 * i) {if (!f[j]) {--count;f[j] = true;}}}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 × ∑ k p ，其中， 2 ≤ k ≤ v

这篇关于质数计数问题求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---