arrays - 查找素数范围内出现次数最多的数字

Question

给定两个数字 a 和 b (1 <= a <= b <= 10^6)。在 a 和 b 之间的所有质数中找到出现次数最多的数字。如果频率相同，则打印最高位。

例子:从1到20，素数是- 2,3,5,7,11,13,17,19。这里2,5,9只出现一次，3,7出现两次，1出现5次。所以结果是 1。

一种基本方法是:

• 在 [a, b] 范围内 - 找到所有素数。
• 取一个计数数组，从 0 到 9 计数出现的次数。
• 对于范围内的所有素数，提取所有数字并在计数数组中相应地增加数字的计数。
• 从计数数组中找出最大值。

但这对于大范围来说效率很低，比如 [1, 1000000]。

有什么有效的方法可以做到这一点吗？

Answer 1

做一个sieve of Eratosthenes找出 0, 10⁶ 范围内的所有质数。这可以非常快地完成(在普通机器上不到 1 秒)。使用 10 个辅助数组 - 每个数组的每个数字一个，大小为 10⁶。如果数字不是素数，则将 0 存储在所有 10 个数组中。如果一个数是素数，则在每个数组中存储给定数字在该数中出现的次数。在对每个数组进行循环并累加 prefix sums 之后给定数字出现的次数。这可以在线性时间内很容易地完成。说数字 3:

for (int i = 1; i < n; ++i) {
   a3[i] += a3[i-1];
}

有了这些数组，您就可以在恒定时间内计算指定时间间隔内每个数字出现的次数。即 3 在区间 [x,y] 中出现的次数是 a3[y] - a3[x-1](注意特殊情况，当 x 是0).

该算法的计算复杂度与埃拉托色尼筛法相同，用于预计算和每个查询的常数。内存复杂度是线性的。您可以通过仅将素数的值存储在辅助数组中来改善内存开销，因此如果需要，它们的大小等于最多 10⁶ 的素数。然而，这会使实现稍微有点棘手。