感謝SA大的意見，讓我把這一題作出來了 舊程式如下: http://homepage.ntu.edu.tw/~b94202058/test09.c 新程式如下: http://homepage.ntu.edu.tw/~b94202058/test09_01.c 舊程式是把B到C每一個數都和A做輾轉相除 新程式根據SA大的意見，先找出A所有的質因數 但做了一點修正，沒有對[B, C]間所有的整數建表 因為當 B=2, C=10000000時，就得建一個40MB的表 TestGirl不會允許程式使用這麼多記憶體 替代的方法是: 先 coprimes = C - B + 1 然後由小到大檢查B到C每一個數 若發現該數可被A的某一個質因數整除，就 coprimes-- 然後我輸入測資: 2 2 100000000 2 2 1000000000 2 2 499999999 根據我用筆電上的cygwin測試的結果 舊程式跑2分37秒 新程式跑1分49秒 相信在資訊系強大的伺服器上一定跑得更快 感謝大家辛勞 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.217.60