c - C 中的段错误，可能在中型/大型动态分配的数组上

Question

注意: 我查看了其他段错误帖子，与我的问题密切相关的是在堆栈上创建大型数组最终导致溢出。但是，正如您从下面的代码中看到的那样，我在堆上进行分配，但仍然遇到这个问题。

我已经使用 Valgrind 和 gdb 对此进行调试，它们告诉我以下内容:下面的函数代码中出现“大小 4 的无效读取 ... numberDivisors”或段错误。奇怪的是，这适用于 49141 之前的所有数字，因为它会在抛出错误或段错误时循环遍历感兴趣的数字。 这仅在它处于循环中时。当我在没有循环的情况下输入一个大数时，它会报告除数的数量而不会出错或出现段错误。任何人都可以在下面的代码中看到问题所在吗？谢谢!

int numberDivisors(int n) {
    int lim = (int)floor(sqrt((double)n));
    int *primes = (int*)calloc(n, sizeof(int));
    int *divisors = (int*)calloc(n, sizeof(int));
    int i, j, ctr;
    ctr = 0;

    if(primes && divisors) {
        for(i = 0; i < n; i++) {
            primes[i] = 1;
            divisors[i] = 0;
        }

        for(i = 2; i < lim; i++) {
            if(primes[i]) {
                for(j = i; i * j < n; j++) {
                    primes[i * j] = 0;
                }
            }
        }

        for(i = 2; i < n; i++) {
            if(primes[i]) {
                if(n % i == 0) divisors[i] = 1;
                for(j = i; i * j < n; j++) {
                    // int result = n % (i * j);
                    assert(i * j < n); //Added at lsk's request.  i * j passes the test.

                    //if(result == 0) {
                    if(n % (i * j) == 0) {
                        if(!divisors[i * j]) {
                            divisors[i * j] = 1;
                        }
                    }
                }
            }
        }

        for(i = 2; i < n; i++) {
            if(divisors[i]) ctr++;
        }

        ctr += 2;
    } else {
        printf("Allocation failed.");
    }
    free(primes);
    free(divisors);
    return ctr;
}

更新 我将函数中的所有 int 都更改为 unsigned long(只是为了看看它是否会起作用)，现在它运行得很好。然而，Umer 是对的 - 我必须重新考虑算法，因为它花费的时间比必要的时间长，但这是另一个问题。感谢 SO 社区的帮助!

Answer 1

错误其实在

if(!divisors[i * j]) {
   divisors[i * j] = 1;
}

由于整数溢出。考虑一个简单的例子:

int n = 123123123;
int i = 57641;
int j = 74495;

printf("i         = %d\n", i);
printf("j         = %d\n", j);
printf("i * j     = %d\n", i*j);
printf("i*1.0 * j = %f\n", i*1.0 * j);
printf("n         = %d\n", n);

产生以下输出:

i         = 57641
j         = 74495
i * j     = -1001001
i*1.0 * j = 4293966295.000000
n         = 123123123

如你所见i * j < n是真的，但是i * j是一个负整数。索引 divisors负索引会导致崩溃。