Scratch & Math: 數字積木(二)

埃拉托斯特尼是西元前三世紀的希臘數學家,他設計出一種有效的篩選法來找出一定範圍內的所有質數,因此聞名於世。在這一章裡我們就要實做埃拉托斯特尼的篩選法來尋找質數。

數學關鍵字: 質數。

數學家:埃拉托斯特尼。

Scratch程式:

有效的質因數測試範圍

如果要判定一個數字n不是質數,概念上必須要找到另一個範圍介於2和(n-1),而且可以整除n的自然數。

事實上,我們可以將搜尋範圍再做進一步的縮小,由2一直搜尋到 時就停止測試。如此一來,測試的上限就會由原本的(n-1)變成 。

例如被除數是101的時候,我們要測試的除數只要是2到 之間的自然數即可。

若數字101有不為1和自身101的因數,一定會介於2到10之間。換句話說,若是2到10之間的自然數都無法整除101,則101就是一個質數。

要證明這個道理,可以假設一個合數n可以被分解為a*b。a和b是大於1的自然數。

n=a*b

同時n的平方根為m,m是大於1的實數。

n=m*m

進一步研究a、b和m的大小關係,會有三種可能性:

1. a > m ⇒ b < m

2. a = m ⇒ b = m

3. a < m ⇒ b > m

在這三種可能性中,a和b中較小的一個數必定會小於等於m,

min(a, b) ≤ m

這就是說如果數字n是一個合數的話,必然存在小於 的因數。因此我們要搜尋數字n的因數時,上限只要測試到 的自然數即可。

動手做8–2 加速的試除法

[程式設計需求規格]

應用有效的質因數測試範圍,求解任一個大於1的自然數n的因數分解。

[程式設計角色和舞台]

由範例庫任意選取一個角色造形。舞台維持空白即可。

[程式設計解決方案]

[程式檢視]

程式[Cat 8–2.1]和程式[Cat 8–1.1]基本上非常近似,除去斷點設定外,唯一的不同點在於程式[Cat 8–2.1]的迴圈檢查範圍上限變為 i> √n ,

輸入和動手做8–1同樣的值1234567887654321,可以得到完全一樣的質因數分解,

1234567887654321 = 3*3*11*37*73*141*137*333667

同時由於搜尋的上限縮小,執行時間只須要0.234秒。相較於動手做8–1程式的執行時間6.254秒快了許多。

埃拉托斯特尼篩選法

埃拉托斯特尼 西元前三世紀的希臘數學家、地理學家,設計出埃拉托斯特尼篩選法找到一定範圍內的所有質數聞名於世。埃氏另一個重要成就是定義經緯度系統,被尊稱為「地理學之父」。(取自維基百科Eratosthenes

古希臘數學家埃拉托斯特尼設計了一種簡單的篩選法來找到一定範圍內的所有質數。

首先設定想要篩選的範圍n,然後對所有小於 √n 的質數進行篩選。所謂篩選就是把質數p留下,但是把所有p的倍數都剔除。

對於小範圍的質數搜尋,埃拉托斯特尼篩選法是一個很有效率的方法。

以搜尋範圍20為例,首先對第一個質數2做篩選:

繼續對質數3做篩選:

質數5已經大於 √20,所以就不須要再做篩選。

至此我們篩選出小於20的質數為:

動手做8–3 實做埃拉托斯特尼篩選法

[程式設計需求規格]

以Scratch程式實做埃拉托斯特尼篩選法,找出所有小於100的質數。

[程式設計角色和舞台]

由範例庫選取數字,並拼貼製做出1–100的數字造型。舞台維持空白即可。

在角色「數字」中必須製做出所有1–100的造型。首先可以從範例庫選用-Glow系列的字母,挑選出數字1–9。

對於大於一位數的數字10–100,可以在Scratch角色造型中利用簡單的繪圖指令以拼貼的方式製做。

第一步要將範例庫的數字0–9都存成磁碟中的檔案。在已經匯入造的數字上按滑鼠右鍵後會出現選單,選取「儲存到電腦」,將選定的造型存入磁碟。這些檔案的副檔名都會是「.svg」。

第二步要從磁碟匯入數字造型。以製做數字100為例,在造型畫布的上方按下「匯入」鈕,從之前儲存的檔案中選取數字1,匯入造型的畫布。

第三步再用同樣的方法從磁碟匯入數字0的造型。當數字0匯入後會和之前匯入的數字1重疊在一起,這個時候用滑鼠選擇數字0往右拉動適當的距離。

第四步再重複匯入第二個數字0,往右拉動就拼貼出數字100。將造型畫布左上方的造型名稱改為「100-glow」。

我們必須耐心地製做出所有的數字造型1–100,並且正確地更改每個造型的名字為「x-glow」。

[程式設計解決方案]

[程式檢視]

在Scratch程式中支援一種特殊的方塊指令叫做分身。分身是角色的一個複製暫存,每一個分身都可以各自獨立執行自己的方塊指令。

按下小綠旗後舞台會依照程式[數字8–3.1]依序顯示排列整齊的數字1–100。每一個數字都是一個分身,也都擁有各自獨特的「分身編號」。由於程式[數字8–3.2]中有檢查數字1,由於數字1不是質數,一開始就縮小為原尺寸的15%。

這時候可以移動滑鼠去點選任意的數字。依照依埃拉托斯特尼篩選法我們先點選最小的質數2,於是觸發了程式[數字8–3.3],變數「滑鼠選擇數字」被設定為2。

逐次再用滑鼠去點選質數3、5、7,就可以篩選出1–100的所有合數。在舞台沒有被縮小的數就是質數,小於100的質數一共有25個。

這25個小於100的質數分別是:2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。

延伸閱讀:

Scratch & Math: 天花板上的蜘蛛(一) 天花板上的蜘蛛(二)

Scratch & Math: 直線裡的宇宙觀(一) 直線裡的宇宙觀(二)

Scratch & Math: 不能說的祕密(一) 不能說的祕密(二)

Scratch & Math: 無理的道理(一) 無理的道理(二) 無理的道理(三)

Scratch & Math: 歡樂派(一) 歡樂派(二) 歡樂派(三) 歡樂派(四)

Scratch & Math: 隱藏在花朶裡的祕密(一) 隱藏在花朶裡的祕密(二)

Scratch & Math: 兔子繁殖是一個好問題 (一) 兔子繁殖是一個好問題 (二) 兔子繁殖是一個好問題 (三)

Scratch & Math: 數字積木(一) 數字積木(二) 數字積木(三)