Fw: [問題] 使用bit來篩檢質數

看板 Prob_Solve
作者
時間
留言 4則留言,2人參與討論
推噓 2  ( 2推 0噓 2→ )
※ [本文轉錄自 Programming 看板 #1Tr9hPFc ] 作者: wa007123456 (大笨羊) 看板: Programming 標題: [問題] 使用bit來篩檢質數 時間: Wed Nov 20 09:45:57 2019 各位好! 這個質數篩檢法是這樣的 假設一個byte變數A是0b11111111 (紀錄1~8中間為質數的判斷,1代表為質數,0代表不是質數 然後透過迴圈計算判斷 不是質數的就改為0 等到執行完成 可以得到變數A的紀錄 再慢慢取出一個一個bit 然後顯示是否為質數(bit值為1) 好處是儲存空間是一般篩檢法的1/32倍 我目前只有比較直觀的寫法: (網頁版程式碼): https://paste.ofcode.org/jianB5guTtNWMVPMsSp7vL ------------------------------------------------------------------------------ int index=0b1111111111111111111111111111111; //假設1~32的所有數 都為質數 for(byte i=2;i<32;i++){ for(byte k=2;k<i;k++) { if (i%k==0){ index&=~(1<<i); //如果i不是質數 就把它對應的位置設為0 break; } } } for(int i=1;i<32;i++) { //輸出為質數的結果 if((index>>i&1)==1) //位元為'1' 代表他是質數 System.out.print(i+" "); } ----------------------------------------------------------------------------- 可是我想再縮短一半的記憶體空間,就是只要是偶數都不可能是質數(除了2) 各位大大有甚麼比較好的改法嗎? 我目前想法是32個位元分別代表奇數不包含偶數 也就是每個bit的位置 所代表的意義變為 1 3 5 7 ..... 2i+1 (其中i正整數) 而不是 1 2 3 4 5 6.....i 這樣 感謝各位大大 --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.162.204 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1574214361.A.3E6.html ※ 編輯: wa007123456 (223.141.162.204 臺灣), 11/20/2019 09:46:39 ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: wa007123456 (223.141.162.204 臺灣), 11/20/2019 09:49:00 ※ 編輯: wa007123456 (223.141.162.204 臺灣), 11/20/2019 09:56:10
2FDJWS: 你的想法挺好的啊 如果還要更好 可以看樓上連結的src頁面 11/20 13:37
3FDJWS: k = { 7, 11, 13, 17, 19, 23, 29, 31 } 11/20 13:38
4FDJWS: 這個方法的名稱叫做 wheel factorization 11/20 13:39