给定两个数字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数组中递增这些数字的计数。
从count数组中找出max。
但这在很大范围内是无效的，比如说[1000000]。
有什么有效的方法可以做到这一点吗？
最佳答案
执行asieve of Eratosthenes以查找范围为0，106的所有素数。这可以很快完成（在一台普通的机器上不到1秒）。使用10个辅助阵列-一个为每个数字的数组中的每一个大小为106。如果一个数字不是素数，则0存储所有10个数组。如果一个数字是素数，则在每个数组中存储给定数字在该数字中出现的次数。在每个数组上循环之后，累积给定数字出现次数的prefix sums。这在线性时间内很容易做到。对数字3说：
for (int i = 1; i < n; ++i) {
a3[i] += a3[i-1];
}
有了这些数组，您可以在固定时间内计算指定间隔内每个数字的出现次数。即间隔
[x,y]中3的出现次数a3[y] - a3[x-1]（注意x为0时的特殊情况）。该算法的计算复杂度与埃拉托色尼的预计算和每个查询的常数的筛选器相同。存储器的复杂性是线性的。只需在辅助数组中存储素数的值，就可以提高内存开销，因此，如果需要的话，它们的素数等于106的大小相等。然而，这将使实现稍微复杂一些。
关于arrays - 在一个质数范围内查找最大出现位数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32823110/