埃拉托色尼筛法 C 实现错误

Question

所以我正在做下一个作业，将输入数字分解为输出中的素数乘法。当它只显示素数 2 时我很困惑，所以我使用这个函数对分配的素数数组进行了适当的控制转储：

long* eratosthen(long max) {
    bool grid[max + 1];

    for(long i = 0; i < max + 1; ++i) {
        grid[i] = true;
    }

    for(long i = 2; i < max + 1; ++i) {
        if(grid[i]) {
            for(long j = i * 2; j < max + 1; ++j) {
                grid[j] = false;
            }
        }
    }

    long *primes;
    primes = (long*)malloc((max + 1) * sizeof(long));

    long index = 0;
    for(long i = 2; i < max + 1; ++i) {
        if(grid[i]) {
            primes[index++] = i;
        }
    }

    return primes;
}

出于某种未知原因，转储仅显示 2 并结束。调用转储由以下代码组成：

int main(void) {
    // Prime numbers get calculated first
    long *primes;
    primes = eratosthen(1000000);

    // Control code
    fprintf(stdout, "Control dump of primes array:\n");
    for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {
        fprintf(stdout, "%li\n", primes[i]);
    }
    int ret = 0;
    /// ...
    return ret;
}

//编辑：所以在你回答完所有问题后，我会将我的问题更新为当前状态。主要程序： int 主要（无效）{ // 首先计算素数长*素数；素数 = eratosthen(1000000);

    // Control code
    fprintf(stdout, "Control dump of primes array:\n");
    for( ; *primes != 0 ; primes++) {
        fprintf(stdout, "%li\n", *primes);
    }
    int ret = 0;
}

生成素数函数：

long* eratosthen(long max) {
    bool *grid;
    grid = (bool*)malloc((max + 1) * sizeof(bool));

    index = 0;
    for(long i = 0; i < max + 1; ++i) {
        *(grid + index) = true;
        index++;
    }

    index = 2;
    index_2 = 2;
    for(long i = 2; i < max + 1; ++i) {
        if(*(grid + index)) {
            for(long j = i * 2; j < max + 1; j += i) {
                *(grid + 2 * index_2) = false;
                index_2++;
            }
            index++;
        }
    }

    long *primes;
    primes = (long *)malloc((max + 1) * sizeof(long));

    index = 0;
    for(long i = 0; i < max + 1; ++i) {
        *(primes + index) = 0;
        index++;
    }

    index = 0;
    index_2 = 2;
    for(long i = 2; i < max + 1; ++i) {
        if(*(grid + index_2)) {
            *(primes + index) = i;
            index++;
            index_2++;
        }
    }

    // free the grid
    free(grid);

    return primes;
}

如前所述，Ubuntu 终端显示以下行：

Neoprávněný přístup do paměti (SIGSEGV) (core dumped [obraz paměti uložen])

翻译成这样：

Forbidden access to memory (SIGSEGV) (core dumped [memory image saved])

这是什么意思以及如何摆脱它？ :(

Answer 1

最简单的代码修复可能是在素数数组的末尾添加标记值 0，并重写 main() 中的检查条件。正如评论中广泛解释的那样，您当前的测试：

for(long i = 0; i < sizeof(primes) / sizeof(long); ++i) {

大错特错。您不得尝试使用 sizeof，因为它根本不会执行您希望它执行的操作。

此代码有效：

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

static
long *eratosthen(long max)
{
    bool grid[max + 1];

    for (long i = 0; i < max + 1; ++i)
        grid[i] = true;

    for (long i = 2; i < max + 1; ++i)
    {
        if (grid[i])
        {
            for (long j = i * 2; j < max + 1; j += i)   // Key fix
                grid[j] = false;
        }
    }

    long *primes;
    primes = (long *)malloc((max + 1) * sizeof(long));

    long index = 0;
    for (long i = 2; i < max + 1; ++i)
    {
        if (grid[i])
            primes[index++] = i;
    }
    primes[index] = 0; // Sentinel

    return primes;
}

int main(void)
{
    // Prime numbers get calculated first
    long *primes = eratosthen(1000000);

    fprintf(stdout, "Control dump of primes array:\n");
    for (long i = 0; primes[i] != 0; ++i)
    {
        printf("%7li", primes[i]);
        if (i % 10 == 9)
            putchar('\n');
    }
    putchar('\n');
    return 0;
}

我修改了代码，每行打印 10 个数字。我在 main() 中更改了循环中的条件。我在函数中做了两个关键更改——一个是正确计算素数的倍数，另一个是在素数列表的末尾添加标记。

它生成一个包含 78,498 个以

开头的素数的列表

      2      3      5      7     11     13     17     19     23     29
     31     37     41     43     47     53     59     61     67     71
     73     79     83     89     97    101    103    107    109    113

并以：

结尾

 999563 999599 999611 999613 999623 999631 999653 999667 999671 999683
 999721 999727 999749 999763 999769 999773 999809 999853 999863 999883
 999907 999917 999931 999953 999959 999961 999979 999983

您可能会注意到该代码并未发布 primes — 可以说应该发布。您可能会注意到分配给质数的 space 大大超过了所需的 space（一百万对少于八万）；您可以使用 realloc() 来缩小分配的 space，或者使用不那么保守（或者我的意思是不那么挥霍？）估计所需的条目数。

埃拉托色尼筛法 C 实现错误

Sieve of Eratosthenes C implementation error

c

implementation

sieve-of-eratosthenes