創作內容

2 GP

【VB】關於質數這玩意兒

作者：小YA│2015-11-29 17:16:27│巴幣：4│人氣：982

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

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

-核心程式碼

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

-執行結果

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

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

最後附上Sieve of Eratosthenes相關資料

喜歡 2 收藏 1 引用留言推上首頁檢舉

引用網址：https://home.gamer.com.tw/TrackBack.php?sn=3030323
All rights reserved. 版權所有，保留一切權利

相關創作

【職業&生活】2024/04/25拜四、生活及工作的平衡&十個要點

希望的力量~ 成年光之美少女+數碼獸'23~

【廢文】《人生看到現在動畫的必看推薦名單》

USD和MaterialX使用經驗分享

烏古爾的TRPG世界臨時成立的團隊

留言共 4 篇留言

一閃一閃派大星：
請問你是怎麼抓後三個質數顯示的?

我的作法是每抓到一個質數就丟進字串內
字串=字串 & " " & 質數 & " "
最後再用SPLIT取最後三項

但是這樣效率足足多了十倍
想問問你的做法[e18]

09-13 15:29

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

一閃一閃派大星：
另外我想問SOE演算法在進行之前應該要先抓一堆質數才能做吧?

我的作法是先判斷2~1000的質數有哪些
再從這些質數下去做SOE

不知道我這個觀念有沒有錯

09-13 16:02

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

一閃一閃派大星：
剛剛說的效率多十倍應該是慢十倍才對
打錯了...

我設定成ARRAY後速度真的快了很多
這個方法我用過好幾次
但這一次我竟然用了一個奇怪的作法
難怪這麼慢

然後目前我SOE的作法是先從2開始抓質數
例如抓出2 3 5 7 11...
然後再用倍數下去刪除4 6 8 10...6 9 12 15 18....14 21 28 35....
所以我問題在於前面那個抓質數的步驟
你的SOE作法也是這樣嗎

09-13 19:18

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

一閃一閃派大星：
原來如此
那我全部明白了
謝謝你喔

09-13 19:32

小YA：
OK Der09-13 20:29

我要留言提醒：您尚未登入，請先登入再留言

2 喜歡★mapleleaf9 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：【VB】點與集合間之鄰近... 後一篇：【VB】字元計數～...

追蹤私訊切換新版閱覽

作品資料夾

xzp83502 給在線巴哈們：
果果日記小屋更新中歡迎進來參觀謝謝^^看更多我要大聲說昨天20:43