电脑解题实作-解题实作.ppt

求質數的改善方法 電腦問題解決-電腦解題實作-解題實作 電腦問題解決-電腦解題實作-解題實作 電腦問題解決-質數問題 第*頁 質數的定義 質數（素數）就是「除了1和本身之外，沒有其他因數的數」。 0和1不是質數！ 例如：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，101，103，107，109，113… 最小的質數是2，也是質數中唯一的偶數（雙數）；其他質數都是奇數（單數）。質數有無限多個，所以不存在最大的質數。 第*頁 質數的定義 正整數 數字1 只有1個因數 質數 只有2個因數 合成數 超過2個因數 第*頁 關於質數 如何找質數呢？大約在兩干多年以前，古希臘數學家埃拉托散尼利用羊皮發明了一種找質數的方法他將一定範圍的數字寫在羊皮上，然後將2、3、5、7等的倍數挖掉，就好像一個上面有許多小孔的篩子，因此被稱為「埃拉托散尼篩法」。目前電子計算機找質數的原理就是根據「埃拉托散尼篩法」。 圍繞著質數存在很多數學問題、數學猜想和數學定理。著名的有孿生質數猜想和哥德巴赫猜想。 第*頁 質數的應用（from wiki） 質數近來被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找質數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。 以質數形式無規律變化的飛彈和魚雷可以使敵人不易攔截 第*頁 質數的應用（from wiki） 在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數最好設計成素數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。 在害蟲的生物生長週期與殺蟲劑使用之間的關係上，殺蟲劑的素數次數的使用也得到了證明。實驗表明，素數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗藥性。 求質數(方法一) 歐基里德已經證明：質數是無窮的！ 以前常見的考題：請求出100以內的所有質數？ 偶數一定有因數2，只算奇數！ 把3~99的數用小於其的數除之判斷可否整除？ 求質數(方法一)流程圖 第*頁 求質數(方法二) 篩掉所有偶數 以陣列建立100內的質數表，先於第一元素放入已知的最小質數2。 用迴圈，把3～100剩下來的奇數（i）除以質數表內≥10的數n，如果上述方法皆無法整除，則i為質數，把i放入質數表。 任意自然數N，N之最大的因數為小於或等於 此題最大數為100，故其最大因數為　　 =10 求質數(方法二)流程圖 第*頁 第*頁 方法一：程式執行的步驟較多，沒效率！ 方法二：節省步驟，較有效率！ 想想看，是否還有更快速的求質數方法？ 求質數的方法比較 電腦問題解決-電腦解題實作-解題實作 電腦問題解決-電腦解題實作-解題實作