C segfaults中的大型阵列,时代的Sievs

Question

所以,我有这个代码.

void main(void){

    int n = 9999;
    int *array = calloc(n, sizeof(int));
    int i, j;

    // Populate array up to N
    for(i = 0; i < n; i++){
        array[i] = 2 + i;
    }

    // Run sievs
    sievs(array, n);

    print_prime(array, n);
}

我的问题是,如果N足够大,程序将核心转储.我的理论是在堆栈上分配了一些东西,并且它不足以容纳那么多数据,但是我使用的是calloc,所以它应该是heep.

这两个打印函数看起来像这样:

void print_prime(int *a, int n){
    int i;
    for (i = 0; i < n; i++){
        if(a[i] != -1)
            printf("Prime: %d \n", a[i]);
    }
}

是否有任何此代码导致它？我不明白为什么.

这是siev功能:

void sievs(int *array, int n){

    int i, j;

    for(i = 2; i <= n; i++){
        if(array[i-2] != -1){
            for(j = i*i; j <= n; j+=i){
                array[j-2] = -1;
            }
        }
    }

}

我看不出有什么不对,但是,我只是在计算机科学的第二年,所以我不是那种经验丰富的C.我试着解决这个问题一段时间了.它适用于小数字.然而,不是大的,我在互联网上读到的一切都表明它可能是堆栈的问题.

这里有什么东西在这里分配？

Answer 1

该程序将崩溃n足够大,因为

j = i * i

将导致j变量(int类型)溢出.因此在

array[j-2] = -1;

该指数j - 2将为负数.

您可以通过j至少声明long或通过使用任意精度库(例如GNU多精度算术库)来解决问题.