I tried counting how many prime there are (except 1 and 0) until there are N number of primes. But somehow my program always ends up looping INFINITELY

int main (){
    int n; 

    printf("Enter size N: ");
    scanf("%d", &n);

    int i, j, ctr = 0, flag = 0; 
        for (i = 2; ctr != n; i  ){
            for (j = 2; j < i; j  ){
                if (i%j==0){
                    flag = 1;
                    break;
                }
            }
            if(flag!=1){
                ctr  ;
            }
        }
    
}

CodePudding user response：

I notice you never reset your flag. So once a divider is found, you raise your flag to indicate it isn't a prime. But never set it back to 0, so all number afterward are considered not prime

int i, j;
int ctr = 0; // Prime number counter
int flag; 
// For i, from 2 to whatever needed to have N prime numbers
for (i = 2; ctr != n; i  ){

    flag = 0 // THIS IS THE LINE YOU'RE MISSING

    // Look for potential divider
    for (j = 2; j < i; j  ){
        // If i is divided by j, it isn't prime
        if (i%j==0){
            flag = 1;
            break;
        }
    }
    // If no divider found, i is prime
    if(flag!=1){
        ctr  ;
    }
}

CodePudding user response：

To add something to your program different than what Portevent mentioned, you dont have to check if i % j != 0 for all j < i to check if i is prime. You just have to check for the range j < sqrt(i).
This is because you stop looping when you get a j value such that i % j == 0. If you were to get to j == sqrt(i) it means for i to not be prime it would have at least a prime factorization of p * q with p and q being greater than sqrt(i), which is nonsense, hence i is prime.
PS: in case you add this optimization to your program, do not hardcode sqrt(i) in the for loop, assign it to some variable then write the variable in the loop to avoid repeated computations.