尋找質數與黃金比例

(本篇文章利用Python實作) 

本文將討論兩個老掉牙的演算法問題
尋找質數與計算黃金比例
並將其實做出來

首先是第一個問題 尋找質數
給定一個上限n 找出從0到n的所有質數
這邊我們用一個最簡單的想法來思考
將所有的合數列出來
再將其與0到n比對
其差集便是質數了
了解想法後 來試著用python做出來吧！

n = int(input("請輸入正數(>2):"))

while n<2:
    n = int(input("請輸入正數(>2):"))

先利用input函數輸入數值
接著有一個簡單的小除錯
大於2以上才開始尋找質數

prime = []
A = []

for i in range(2, int(n**(1/2))+1):
    for j in range(2*i, n, i):
        A.append(j)
        
for x in range(2,n):
    if x not in A:
        prime.append(x)
        
print(prime)

接著就是將所有倍數都列出來
我們只需檢查到根號n的值就夠了
接著將所有的值放進list A中
接著讓他跟0到n比對
如果值不在A中 便是質數了

------------------------------------------------------------------------------------------------------------------------------------

接著是黃金比例
其實黃金比例可以利用很多方式來定義
這邊我們利用費波那契數列 (Fibonacci numbers) 連續兩數的比值來逼近
這篇文章有較詳細的數學解釋
有興趣的同學可以看看
https://www.taiwannews.com.tw/ch/news/3487309

本篇文章專注在演算法上
我們假定問題為
找出費式數列中
連續兩數的比值與黃金比例的差距在小數點後30位
找出該兩個數
並計算出黃金比例

GR = (1+5**(1/2))/2

F = [1, 1]
initial_ratio = F[-1]/F[-2]

while abs(GR - initial_ratio) > 10**(-30):
    Fn = F[-1]+F[-2]
    F.append(Fn)
    initial_ratio = F[-1]/F[-2]

print(F[-1], F[-2])
print(F[-1]/F[-2])

首先給定黃金比例的值
接著給定費式數列的最前面兩個數
才能開始自動迭代計算之後的值
接著list的slice
如果要從後面取值 便是利用[-1]的方式

接著開始讓他自己計算
當差距大於10的-30次方時
便會找出下一個費式數列的值並計算前後兩個的比值
最後印出此2數及其比值

因此今日學到的有：
質數的尋找
利用費式數列逼近黃金比例

為來會繼續分享各式作品給大家囉~