CODEWITHSUNDEEP
carraysloopsinfinite
NyxTheShield
NyxTheShield

Reputation: 69

Clueless: Infinite Loop in C

i am working on a c implementation of Eratostenes method of finding prime numbers and i am running into a very weird error.

int* criba(int n){

    int *array;
    int i,j,k,valor;
    array = malloc(n*sizeof(int));

    for (i=0;i<=n-2;i++){
        array[i]=i+2;
    }

    for (j=0;j<n-2;j++){
        valor = array[j];
        for (k=1;valor*k+j<n-2;k++){

            printf("%d \n",array[valor*k+j]);

            }
        }
    }


    return array;
}

This works as intended, it creates an n-2 sized array, with all the numbers from to 2 to n, then it checks every value and prints all of its multiples inside the array (Eratostenes's method seeks for all the multiples of a number starting from 2 and marks them in a table, then it goes to the next unmarked number, after that, all the unmarked number are prime numbers)

The problem is, when i try to zero the numbers to "mark" them, i get stuck in a loop for no reason at all:

int* criba(int n){

    int *array;
    int i,j,k,valor;
    array = malloc(n*sizeof(int));

    for (i=0;i<=n-2;i++){
        array[i]=i+2;
    }

    for (j=0;j<n-2;j++){
        valor = array[j];
        for (k=1;valor*k+j<n-2;k++){
            if (array[valor*k+j] != 0){
                printf("%d \n",array[valor*k+j]);
                array[valor*k+j] = 0;
            }
        }
    }


    return array;
}

In fact, the only problem is array[valor*k+j] = 0;, if i remove that the program returns sucesfully, but with that line it gets stuck and i can't find why. Any help is greatly appreciated.

Upvotes: 1

Views: 109

Answers (2)

RobP
RobP

Reputation: 9522

You are looping forever because of the combination of valor = array[j] and array[valor*k+j] = 0; the inner loop zeroes out some later entries. Then on a future iteration of the outer loop, array[j] has already been zeroed, so valor = 0, so the inner loop test is (0 * k) + j < n-2 where j is held constant which is always false.

The simplest solution is do one pass to print the results, then a separate pass to loop through and zero things out.

Upvotes: 2

pabdulin
pabdulin

Reputation: 35235

Obviously at some moment valor = array[j]; will make valor equal to 0, so the condition in loop valor*k+j < n-2; will always be true, hence the infinite loop.

Upvotes: 3

Related Questions