感謝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