2009年11月22日 星期日

UVa 10533 Digit Prime

最近都在研究質數問題

本題因為IO量極大
原本只建了質數表,發現不夠快(TLE)
索性連DigitPrime累計表也建起來
dpCum[n]: 從0~n 累計總共有幾個Digit Prime
這樣每筆測資的時間就降到O(1)

這陣子學了不少質數的技巧
像是這題用的高速篩法

像這種百萬等級的問題,建表都很快
另一題大到十億左右,建表就太慢了