2

Sieve の方法を使用して、20 億までのすべての素数をリストする次のコードを作成しました。フラグを立てる目的でビットマスキングを使用しました。素数を正しく取得できますが、最初のいくつかの素数が毎回欠落しています。プログラムのバグを見つけるのを手伝ってください。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

#define MAX 2000000000

char* listPrimes(){
int block = sqrt(MAX);
char* mark = calloc((MAX/8),sizeof(char));
int i = 2;
int j;
char mask[8];
for(j=0;j<8;j++)
    mask[j] = 0;
mask[7] = 1;
mask[6] |= mask[7] << 1;
mask[5] |= mask[7] << 2;
mask[4] |= mask[7] << 3;
mask[3] |= mask[7] << 4;
mask[2] |= mask[7] << 5;
mask[1] |= mask[7] << 6;
mask[0] |= mask[7] << 7;

for(j=0;j<8;j++)
    printf("%d ",mask[j]);
mark[0] |= mask[0];
mark[0] |= mask[1];

while (i < block){

        for (j = 2; i*j <= block; j++)
                mark[(i*j) / 8] |= mask[((i*j) % 8 )];
        i++;
    }
printf("\n");
printf("The block size is\t:\t%d\n",block);


j = 2;
while(j<=block){
    if((mark[j / 8] & mask[j]) == 0 ){
        for(i = 2;i <= MAX; i++){
            if((i%j) == 0){
                mark[i / 8] |= mask[(i % 8)];
            }
        }
    }
while((mark[++j / 8] & mask[j % 8]) != 0);
}


for(j=0;j<=MAX;j++)
        if((mark[j / 8] & mask[(j % 8)]) == 0)
            printf("%d\n", ((8*(j / 8)) + (j % 8)));

return mark;
}   

int main(int argc,char* argv[]){

listPrimes();

return 0;
}
4

3 に答える 3

1

ArunMKが言ったように、2 番目のループでwhileは、素数j自体を の倍数としてマークしますj。Lee Meadorが言ったようjに、インデックスにはモジュロ 8のモジュラスを使用する必要がありmaskます。そうしないと、範囲外にアクセスして未定義の動作を呼び出します。

未定義の動作を呼び出すもう 1 つのポイントは次のとおりです。

while((mark[++j / 8] & mask[j % 8]) != 0);

jシーケンスポイントを介在させずに使用および変更する場所。と書くことで回避できます。

do {
    ++j;
}while((mark[j/8] & mask[j%8]) != 0);

whileまたは、本文が空のループを主張する場合

while(++j, (mark[j/8] & mask[j%8]) != 0);

コンマ演算子を使用できます。

mark[MAX/8]に割り当てられていないものにアクセスすることにより、より未定義の動作

for(i = 2;i <= MAX; i++){

と

for(j=0;j<=MAX;j++)

また、charが符号付きで 8 ビット幅の場合、

mask[0] |= mask[7] << 7;

の結果であるため、実装定義です（実装定義のシグナルを発生させる場合があります）。

mask[0] | (mask[7] << 7)

(the int128) は として表現できませんchar。

whileしかし、2 番目のループで境界の平方根を超えないすべての素数で各数値を除算するのはなぜですか?

    for(i = 2;i <= MAX; i++){
        if((i%j) == 0){

これにより、アルゴリズムはエラトステネスのふるいではなく、試行分割になります。

whileそこでも最初のループのテクニックを使ってみませんか？(そして、なぜ 2 つのループがあるのでしょうか?)

while (i <= block){
    if ((mark[i/8] & mask[i%8]) == 0) {
        for (j = 2; i*j < MAX; j++) {
            mark[(i*j) / 8] |= mask[((i*j) % 8 )];
        }
    }
    i++;
}

オーバーフローせず ( の指定された値がMAXとして表現可能である場合int)、正確な出力オーダーがより速く生成されます。

于 2013-01-08T21:53:34.627 に答える
1

中央のループを変更してモジュロを追加します。

j = 2;
while(j<=block){
    if((mark[j / 8] & mask[j % 8]) == 0 ){
        for(i = 2;i <= MAX; i++){
            if((i%j) == 0){
                mark[i / 8] |= mask[(i % 8)];
            }
        }
    }
}
于 2013-01-08T17:55:00.670 に答える
1

2 番目の while ループでは、2 以降の i をループし、if (i%j == 0). これは、i が素数の場合にも当てはまります。(i != j) を確認する必要があります。上記で報告されているモジュロも。したがって、次のようになります。 if ((i%j == 0) { if (i!=j) mark[i/j] |= mask[i%j]; }

于 2013-01-08T19:37:40.363 に答える