Nested loop

Question

I got this code from a web and it will return a prime number. But I don't know why. Could someone explain this for me...
https://code.sololearn.com/cqP8blqn4iRJ/?ref=app

Answer 1

That code checks if all numbers from 2 to 100 are prime and any that are get printed.

The outer loop is obviously a loop of i from 2 to 100.

The inner loop is more interesting. It loops j from 2 to the square root of i.
A prime number is a positive integer that is divisible by itself and one but no number between. Looping j from 2 to sqrt(i) is still correct because all non-prime integers are divisible by an integer that is less than or equal to their square root. If x was divisible by a number y that is greater than sqrt(x), y * (some number less than sqrt(x)) = x. For example, 12 is divisible by 6 because 6 * 2 = 12. sqrt(12) = roughly 3.46.

The code doesn't use a square root function, though. The expression j <= (i/j) becomes false after j is greater than square root, though.
Trace for i = 49. For j from 2 to 6, j < i/j is True.
When j is 7, j <= i/j simplifies to: 7 <= 49/7 or 7 <= 7. That's still True.
If the expression was evaluated with j = 8 which is 1 greater than sqrt(49), 8 <= 49/8 simplifies to 8 <= 6.125 which is False.

Also, note that not(i%j) is the same as i % j == 0. % is the modulus operator which returns remainder after division.

Answer 2

I still don't understand, why the code is still running even though it has been breaking

Answer 3

Josh Greig what happened actually when i%j is equal to 0...