Eratosthenes Prime (C) 的 Valgrind 错误

Question

我编写了这个程序来使用 Eratosthenes 方法计算最大 len 的素数。该程序运行良好，我什至可以计算非常大的数字，如 999,999 等等，我得到了很好的输出。但问题是 valgrind 总是向我显示错误，无论 len 有多大或多小。

节目：

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

int main(){
    size_t len=100;
    int *array=malloc(len * sizeof(*array));

    // initialize all elements to 1
    for(int i=0;i<len;i++)
        array[i]=1; 

    //set multiples of array[a] to 0
    for(int a=2;a<len;a++){
        for(int b=2;b<len;b++){
            if(a*b>len)
                break;
            array[a*b]=0;
        }
    }

    //print the index of "1"s in the array
    for(int a=2;a<=len;a++){
        if(array[a]==1)
            printf("%d ", a);
    }
    printf("\n");

    free(array);
    return 0;
}

错误：

我编译使用：gcc -std=c99 -Wall -g test.c -o test
输出：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
gdb 没有显示错误或故障
valgrind ./test 显示：

==10134== Invalid write of size 4
==10134==    at 0x400695: main (...)
==10134==  Address 0x52041d0 is 0 bytes after a block of size 400 alloc'd
==10134==    at 0x4C2DB8F: malloc (...)
==10134==    by 0x400625: main (...)
==10134== 
==10134== Invalid read of size 4
==10134==    at 0x4006D9: main (...)
==10134==  Address 0x52041d0 is 0 bytes after a block of size 400 alloc'd
==10134==    at 0x4C2DB8F: malloc (...)
==10134==    by 0x400625: main (...)
==10134== 
 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 
==10134== 
==10134== HEAP SUMMARY:
==10134==     in use at exit: 0 bytes in 0 blocks
==10134==   total heap usage: 2 allocs, 2 frees, 1,424 bytes allocated
==10134== 
==10134== All heap blocks were freed -- no leaks are possible
==10134== 
==10134== For counts of detected and suppressed errors, rerun with: -v
==10134== ERROR SUMMARY: 8 errors from 2 contexts (suppressed: 0 from 0)

正如您在代码中看到的那样，我将我的数组声明为 int *array=malloc(len * sizeof(*array));， 在我看来 是问题所在。如果我这样声明：int array[len];，valgrind 不会向我显示少量 len 的错误，这也是让我着迷的地方。带有 VLA 声明的更多 len 会导致某些意外行为。那么这里发生了什么？代码有什么问题吗，或者我可以简单地忽略 valgrind 错误，因为输出正常吗？另外，正如我之前所说，该程序适用于非常大的数字，如 999,999，但运行 valgrind 对于 len 在 valgrind 中恰好给出 999,999 错误。非常感谢任何解释:)

Answer 1

你的malloc是正确的，sizeof(*array)和sizeof(int)是一样的，因为*array是一个int.

for(int a=2;a<=len;a++) 溢出 array 因为 array[len-1] 是数组中的最后一个元素，最终你会

if(array[a]==1)
   printf("%d ", a);

与 a==100 超出范围。

应该是

for(int a=2;a<len;a++)
    if(array[a] == 1)
        printf("%d ", a);

编辑

正如在评论中指出的那样，

if(a*b>len)
    break;

if也错了。对于 a==2 和 b==50 你有 a*b==100 不大于比 len 并且您再次越界访问。条件应该是

if(a*b >= len)
    break;

Answer 2

关于您的代码的两条评论：

这里实现的算法并不完全是被称为Erathostenes 筛法 的算法，因为如果你分析你的代码，你会发现你有两个循环，运行 a 和 b 的所有可能值并将它们标记为复合值。是的，你用筛子完成……但这不是 Erathostenes 的高效筛子。 Erathostenes 筛法包括获取下一个未标记的元素，并标记所有元素的倍数（直到达到最大索引，在 len），这类似于：

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

#define N 10000
#define sqrt_N 100

int array[N];

int main(){

    int a, b;
    /* better to leave them at 0 and marking with ones */
    // initialize all elements to 1
    //for(int i=0;i<len;i++)
        //array[i]=1; 

    //set multiples of a to 1
    /* We only need to do this upto sqrt_N because if a unmarked number
     * is discovered above sqrt_N it will be marked (as compund) because
     * it was the product of a number less than sqrt_N or be prime (because
     * it cannot be the product of two numbers greater than the sqrt(N)
     * or it would be greater than N. */
    for(a = 2; a < sqrt_N; a++){
        if (array[a] == 0) { /* do the inner loop only if a is a prime */
            for(b = 2; a * b < N; b++)
                array[a * b] = 1;
        }
    }

    //print the index of "0"s in the array
    for(a = 2; a <= N; a++){
        if(!array[a])
            printf("%s%d", a == 2 ? "" : ", ", a);
    }

    printf("\n");

    //free(array); /* array is no more dynamic */
    return 0;
}

只需检查计算时间，您就会发现它比您的运行速度更快。

你在这样的声明中遇到的问题：

int sieve[999999];

是，如果你把它作为一个局部变量放在 main() 上（就像你做的那样），它将被存储在堆栈中，所以这意味着你需要至少一百万个整数（大小4，最有可能），这是堆栈中的 4 兆字节。我实际上并不知道你使用的是什么操作系统，但堆栈大小是有限的（大约 4-10 Mb）是很常见的，所以如果你不注意你的自动大小，你可能会溢出堆栈变量。

来自 valgrind(1) 的无效写入消息来自您编写了以下代码这一事实：

if (a*b > len) break;

这意味着，在 a*b 结果恰好 len 的可能情况下，您正在写入超出 [=22 范围的数组单元格 array[len] =]（其中一个，他们从 0 到 len - 1）你必须将该行更改为：

if (a*b >= len) break;

或

if (a*b < len) {
    array[a*b] = 0;
}

Eratosthenes Prime (C) 的 Valgrind 错误

Valgrind Error for Eratosthenes Prime (C)

c

valgrind

节目：

错误：