給定兩個數字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]是低效率的。
有沒有做到這一點任何有效的方法?
我不認爲你可以做得更好。 – Henry
@Henry不是針對單個查詢。但是,如果有多個這樣的查詢,可以通過預計算來改進幼稚的方法 –
您的基本方法「低效」在什麼意義上? –