CODEWITHSUNDEEP
c
Daniel Gilbert Dela Peña
Daniel Gilbert Dela Peña

Reputation: 19

counting prime numbers infinite loop

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++;
            }
        }
    
}

Upvotes: 2

Views: 357

Answers (3)

Ufuk Bakan
Ufuk Bakan

Reputation: 118

Who told you that your program loops infinitely? It doesnt. You just missed resetting the flag like others specified. And also:

you can loop for j < i/2;

Think about it: what is the biggest integer divisor of a prime/non-prime number other than self?

To find it out divide it by the possible minimum integer number:

if we divide it by 1 we get the number itself *

if we divide it by 2 we get the half of the number which is the possible maximum divisor.

Upvotes: -1

carce-bo
carce-bo

Reputation: 495

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.

Upvotes: 0

Portevent
Portevent

Reputation: 744

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++;
    }
}

Upvotes: 2

Related Questions