在質數範圍內查找最大出現位數

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 如果需要的話提高內存開銷。但是，這會使實現稍微複雜一些。