0

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

我已经使用 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 社区的帮助！

4

1 回答 1

5

错误实际上在

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使用负索引进行索引会导致崩溃。

于 2013-10-05T17:59:26.097 回答