C program with nested loop to get prime numbers

Question

Hello Gurus of programming, I've been learing C programming and I encountered an example in a tutorial to get the list of prime numbers from 2 to 100. but I cannot understand the nested loop condition.

#include <stdio.h> 

int main ()
{ /* local variable definition */ 
    int i, j;

    for(i=2; i<100; i++)
    { 
        for(j=2; j <= (i/j); j++) 
            if(!(i%j))
                break; // if factor found, not prime 
        if(j > (i/j))
            printf("%d is prime\n", i); 
    }

    return 0; 
}

I don't get the second condition

for(j=2; j <= (i/j); j++) 

also if there is no braces on the nested loop, that means that only the following line after the "for" will be executed, correct?

Thank you!

Answer 1

for(j=2; j <= (i/j); j++) // efficient way to say j <= square root of i
    if(!(i%j)) break; // if factor found, not prime 

Starting at 2, and going up to the square root of i, check to see if i is divisible by j.

The reason for this is if no integer less than or equal to the number's square root can evenly divide the number, we know it's not going to match anything bigger.

Think about it. If we know 17 isn't divisible by 2, 3, or 4, we know it's prime, because to be divisible by two numbers greater than 4, it'd have to be at least 25.