@ggg0820 1 May 2022

接上篇 https://noise.cash/post/9zj4zm9sw33n 第一題：寫個程式計算第n個質數是多少 第二題：寫個程式計算費氏數列第(2^2022)項的十進位末三位數字 經過一段時間的沉思，我終於悟了！！ 第一題的想法是這樣的： 參考連結：https://zh.wikipedia.org/wiki/埃拉托斯特尼篩法 如果要找出100以內所有的質數，先寫一個list把2~100都放進去，採用刪去法，把質數的倍數（除了1倍也就是質數本身）都刪掉，留下來的就一定是質數。 100開根號是10，所以只要把10以下的質數都過濾一次就可以了。 首先是2，2是質數，所以把4、6、8...100都刪掉，再來是3，3是質數，所以把6、9、12...99都刪掉。 過程中會有重複刪除的數字沒關係，因為是刪除所以只要確認有刪除掉就可以了 一直到7，7也是質數，重複以上步驟；7之後是8、9、10，都已經被刪除了，而這時10^2 ≥ 100，所以不需要測試11，這時還留在list 裡的數字都是質數。 這個算法為什麼會快？因為可以透過語法yield 把數值存進去不用重複計算，算出100內所有質數後就能接著算10000內所有質數，因為100×100=10000，這個擴張速度是平方成長，10000算完就會跳到1億，依此類推。而計算第幾個也很簡單，弄個邏輯判斷list長度就可以了。 第二題，上一篇留言底下有人提出了不同想法，首先來看看2^2022這個數字有多大： 2022 (log 2 )≈608， 意思是這是一個609位的數字。就當他是10^608好了。 如果用一台時脈5.0GHz的電腦(一秒能處理5億個指令)來算普通的費氏數列遞迴，10^608 ÷ ( 24×60×60×5×10^8）= 10^608÷(4.32×10^13) ≈ 10^594 （天）才會跑完 猩球崛起有演示過怎麼移河內塔，64層河內塔要移動2^64-1步，如果一天移一步，移完就要世界末日了；而這邊的10^594天，絕對是算到宇宙毀滅都算不出來。那怎麼寫呢？ 首先，可以觀察到費氏數列可以用2×2矩陣生成： ［(1,1) , (1,0)］的n次方，會產生費氏數第(n-1)項、第n項和第n+1項。 所以可以用矩陣的概念快速算出2^2022項，最多只要計算2022次就有答案！ 附圖是我的程式碼，用python跑的，因為python可以用內建的swap（比較懶）： a , b = b , a+b 這樣就是普通的費氏數列寫法了，不用再設一個暫存做交換。這樣的算法複雜度是 log n，應該是最快的算法了，要再加快可以用賦值方式設定第64項，因為2022=6×337，2^6=64， 2^2022=64^337。 在上篇也有人用excel做出來，發現到1500項會循環一次。如果知道了1500項會循環，那就可以使用Euler's theorem或是數論的小技巧快速計算餘數。 畢竟2^2022這個數實在太大了，如果能找到規律就能把數字縮小。 在計算中要注意設定數字取末3位，如果沒有取末三位一下就溢位算不出來了。 圖片裡打錯啦：if d&1 ==1: q=(p*b+q*c)%1000 這樣才對