[問題] 篩法算個數 [已解決]

[EdisonX (閉上眼的魚)]

篩法大家都知道，這裡就不介紹了。
小弟遇到的問題是，想直接在篩法過程中，直接再計算有幾個質數，
概念上是先算 [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
→ linotwo:j 有可能是 2 或 3 的倍數，但 p[j] 卻不為 0。
→ EdisonX:對唷,所以還要再判斷 j%2 , j%3,這樣下來倒不如從頭poll.
→ EdisonX:謝謝 linotwo :)
→ EdisonX:補一下,j不可能是2的倍數了,等下再實作,再次感謝.
→ EdisonX:修改後已無誤，謝謝指導，感激不盡。
※ 編輯: EdisonX         來自: 180.177.76.161       (11/23 20:13)