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

13th Aug 2020, 6:39 AM
Paulus Jolan Power Saputra .S
Paulus Jolan Power Saputra .S - avatar
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.
13th Aug 2020, 2:38 PM
Josh Greig
Josh Greig - avatar
0
I still don't understand, why the code is still running even though it has been breaking
15th Aug 2020, 3:54 AM
Paulus Jolan Power Saputra .S
Paulus Jolan Power Saputra .S - avatar
0
Josh Greig what happened actually when i%j is equal to 0...
15th Aug 2020, 3:54 AM
Paulus Jolan Power Saputra .S
Paulus Jolan Power Saputra .S - avatar