Your code is looping over all integers from 2
to 99
, holding the actual number in i
.
for(i = 2; i<100; i++)
Then, for every number i
, the code is looping again over all integers from 2
to (i/j)
.
for(j = 2; j <= (i/j); j++)
Your loop’s finishing condition is mathematically equivalent to j
being smaller than the square root of i
, since any larger integer j
would already contain itself a smaller factor of i
.
(To check this, get a paper and rewrite the inequality so hat i
is the sole part of the right hand side of your condition.)
Then it checks whether or not j
divides i
.
(i%j)
If j
is a factor of i
, then i
modulo j
is zero and hence
if (!(i%j))
evaluates to true
(since 0
is evualted as false
and !
negotiates this) and you can break out of the loop since i
has a divisor not being 1
or i
, hence i
is not a prime.
On the other hand, if the inner loop is finished, you have found a prime since it has only 1
and i
as divisor.
Needles to say that this bruteforce approach is very slow for large integers (you won’t crack RSA with that), but does this clarify your questions?
1
solved this is a program to find prime numbers from 2 to 100 in C [closed]