[問題] 篩法算個數 (已解決)
篩法大家都知道，這裡就不介紹了。
小弟遇到的問題是，想直接在篩法過程中，直接再計算有幾個質數，
概念上是先算 [1,N] 裡有幾個是 6n+1 / 6n+5 之數
(N+1)/6*2-( (N%6==0) || (N%6==5))
再進行扣除，這樣就不用篩完時還要從頭到尾 polling 一遍，
程式碼如下。
typedef unsigned char byte;
byte * se_6n2(size_t N, size_t *cnt)
{
size_t PrimeCnt;
size_t i, j, end, gap;
byte* p=(byte*)malloc(N+1);
PrimeCnt = 2+(N+1)/6*2-( (N%6==0) || (N%6==5));
if(p==NULL){
*cnt=0;
return NULL;
}
memset(p, 1, N+1),p[0]=p[1]=0;
end = (size_t)ceil(sqrt((double)N));
for(gap=4, i=5; i<=end;gap^=6, i+=gap)
if(p[i])
for(j=i*i; j<=N; j+=(i<<1))
PrimeCnt-=p[j], p[j]=0;
*cnt = PrimeCnt;
return p;
}
建表正常，驗證時會先去除 2.3 倍數，不過算出來的個數一直都偏低
N = 100 --> 25 , 算 22
N = 1000 --> 168 , 算 100
N = 10000--> 1229, 算 292
請教是否為我邏輯上有所錯誤？還是必須再回頭重新 polling ?
謝謝各位不吝賜教。
--
就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮，
永遠當老闆的傀儡 你是不是想這麼做？
是的話你就拿回去~ 拿啊！！
九世宅男 : 下輩子不要再讓我幹工程師了 ~
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
→
11/23 18:20, , 1F
11/23 18:20, 1F
→
11/23 18:35, , 2F
11/23 18:35, 2F
→
11/23 18:35, , 3F
11/23 18:35, 3F
→
11/23 18:38, , 4F
11/23 18:38, 4F
→
11/23 20:12, , 5F
11/23 20:12, 5F
※ 編輯: EdisonX 來自: 180.177.76.161 (11/23 20:13)