C 语言中的分段错误，可能在中型/大型动态分配的阵列上

Question

注意：我查看了其他分段错误发布，与我的问题密切相关的是当在堆栈上创建大型数组最终导致溢出时。 但是，正如您从下面的代码中看到的那样，我正在堆上分配并且仍然遇到此问题。

我已经使用 Valgrind 和 gdb 来调试它，他们告诉我以下内容：有一个"大小为 4 的无效读取......数字除数"或以下函数代码中发生的分段错误。 奇怪的是，这适用于 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 更改为无符号长(只是为了看看它会起作用(，它现在运行良好。 然而，Umer是对的 - 我必须重新考虑算法，因为它花费的时间比必要的要长，但这是另一个问题。 感谢您对SO社区的帮助！

Answer 1

错误实际上在

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

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

int n = 123123123;
int i = 57641;
int j = 74495;
printf("i         = %dn", i);
printf("j         = %dn", j);
printf("i * j     = %dn", i*j);
printf("i*1.0 * j = %fn", i*1.0 * j);
printf("n         = %dn", n);

这将产生以下输出：

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

如您所见i * j < n为真，但i * j为负整数。使用负索引divisors编制索引会导致崩溃。