日誌2015-11-29 17:16

【VB】關於質數這玩意兒

題目說明：輸入一正整數N，求出介於≦N的所有質數。

程式分析：這題是剛學習程式語言時都會遇到的一道經典題，而第一個想到的解題方法不外乎就是採用暴力解(意指從2到N，每個値都從2開始除到sqrt(i)，看有沒有可以整除的値在判斷)，不過這邊我不採用這種解法，而是使用Sieve of Eratosthenes演算法，並計算該演算法與暴力解之效率差別。

-核心程式碼

(在Sieve of Eratosthenes質數表的部份我沒有進行Boolean陣列重置的動作，因為這樣可降低執行上的時間)

-執行結果

以輸入777777而言，暴力解的速度就足足慢了約22倍

那麼在來試試更大一點的値：7777777，面對越大的値，暴力解的速度也顯得非常沒有效率，而這次暴力解的速度約為SoE質數表的73倍之慢...

最後附上Sieve of Eratosthenes相關資料

2

4

LINE 分享

相關創作

群狼之證2 • 新參賽者 • 克里斯蒂亞諾·羅納度

聖托里尼 萬神殿豪華版 開箱＋介紹

【yotoo】250329

留言

• 2016-09-13 15:29一閃一閃派大星：
  請問你是怎麼抓後三個質數顯示的?
  
  我的作法是每抓到一個質數就丟進字串內
  字串=字串 & " " & 質數 & " "
  最後再用SPLIT取最後三項
  
  但是這樣效率足足多了十倍
  想問問你的做法

  2016-09-13 18:54小YA：記得我當初是用一個陣列Array(2)，跟一個陣列計數Count
  只要發現一個質數就放進Array(Count\3)，然後每放一個Count就+1
  最後把Array(0~2) Print出來就可以了

• 2016-09-13 16:02一閃一閃派大星：
  另外我想問SOE演算法在進行之前應該要先抓一堆質數才能做吧?
  
  我的作法是先判斷2~1000的質數有哪些
  再從這些質數下去做SOE
  
  不知道我這個觀念有沒有錯

  2016-09-13 18:57小YA：不用啊，從2開始，把2的倍數刪光，接著把3的倍數刪光
  之後到4就會略過，因為已經在2的倍數裡被刪掉了
  這樣一直下去最後剩下的就只會是奇數囉

• 2016-09-13 19:18一閃一閃派大星：
  剛剛說的效率多十倍應該是慢十倍才對
  打錯了...
  
  
  我設定成ARRAY後速度真的快了很多
  這個方法我用過好幾次
  但這一次我竟然用了一個奇怪的作法
  難怪這麼慢
  
  
  然後目前我SOE的作法是先從2開始抓質數
  例如抓出2 3 5 7 11...
  然後再用倍數下去刪除4 6 8 10...6 9 12 15 18....14 21 28 35....
  所以我問題在於前面那個抓質數的步驟
  你的SOE作法也是這樣嗎

  2016-09-13 19:26小YA：可以省去抓質數的步驟
  流程僅是這樣
  從2開始，如果這個數在Boolean裡是True(預設為質數)的話，就把他倍數砍光(全部倍數都改成False)
  每往下一個數就對一下是True是False就行
  

• 2016-09-13 19:32一閃一閃派大星：
  原來如此
  那我全部明白了
  謝謝你喔

  2016-09-13 20:29小YA：OK Der

• 送出