作者wa007123456 (大笨羊)
看板Prob_Solve
标题Fw: [问题] 使用bit来筛检质数
时间Wed Nov 20 09:49:00 2019
※ [本文转录自 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://webptt.com/cn.aspx?n=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
2F：推 DJWS: 你的想法挺好的啊 如果还要更好 可以看楼上连结的src页面 11/20 13:37
3F：→ DJWS: k = { 7, 11, 13, 17, 19, 23, 29, 31 } 11/20 13:38
4F：→ DJWS: 这个方法的名称叫做 wheel factorization 11/20 13:39