0

# Nested loop

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

3 Answers

+ 2

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.

0

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

0

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