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具有负折射率导致崩溃.