在质数范围内查找最大出现位数

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之间的出现次数。
• 对于范围中的所有素数，提取所有数字并相应地在count数组中增加数字的计数。
• 找出从计数阵列最大。

但是这对于大范围说[1，1000000]是低效率的。

有没有做到这一点任何有效的方法？

Answer 1

做一个sieve of Eratosthenes找到范围0,10 范围内的所有素数。这可以很快完成（在一台适度的机器上不到1秒）。使用10个辅助阵列 - 每个阵列大小为10 。如果数字不是素数，则0存储全部10个数组。如果数字是素数，则在每个数组中存储给定数字出现在数字中的次数。之后，在每个阵列上循环并累计给定数字的出现次数。这可以在线性时间内很容易地完成。说对位3：

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

那些具有阵列可以算在恒定的时间指定的时间间隔的每个数字的出现的次数。即3出现在间隔[x,y]数为a3[y] - a3[x-1]（当x是0照顾特例的）。

该算法的计算复杂度相同的预计算和常数为每个查询埃拉托塞尼的筛子中的一个。内存复杂度是线性的。可以通过仅存储在辅助阵列中的素数的值，因此与大小等于素数的数量的具有他们最多10 如果需要的话提高内存开销。但是，这会使实现稍微复杂一些。