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

更改中间循环以添加模数：

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

在第二个 while 循环中，您从 2 开始循环 i 并执行if (i%j == 0). 当 i 也是素数时，这也适用于 i。您需要检查 (i != j)。也是上面报道的模数。因此它变成： if ((i%j == 0) { if (i!=j) mark[i/j] |= mask[i%j]; }

于 2013-01-08T19:37:40.363 回答
1

正如ArunMK所说，在第二个while循环中，您将素数j本身标记为j. 正如Lee Meador所说，您需要j为索引取模 8的模数mask，否则您访问越界并调用未定义的行为。

调用未定义行为的另一点是

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)

( int128) 不能表示为char.

while但是，为什么要在第二个循环中将每个数字除以不超过边界平方根的所有素数？

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

这使您的算法不是埃拉托色尼筛，而是一个试验部门。

你为什么不使用第一个while循环中的技术呢？（然后，为什么要两个循环？）

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 回答