UVa 10533 Digit Prime
最近都在研究質數問題
本題因為IO量極大
原本只建了質數表,發現不夠快(TLE)
索性連DigitPrime累計表也建起來
dpCum[n]: 從0~n 累計總共有幾個Digit Prime
這樣每筆測資的時間就降到O(1)
這陣子學了不少質數的技巧
像是這題用的高速篩法
像這種百萬等級的問題,建表都很快
另一題大到十億左右,建表就太慢了
本題因為IO量極大
原本只建了質數表,發現不夠快(TLE)
索性連DigitPrime累計表也建起來
dpCum[n]: 從0~n 累計總共有幾個Digit Prime
這樣每筆測資的時間就降到O(1)
這陣子學了不少質數的技巧
像是這題用的高速篩法
像這種百萬等級的問題,建表都很快
另一題大到十億左右,建表就太慢了
留言
張貼留言