Prime Numbers with While and For

Question

I don’t understand how a command finds prime values:

for i in range(2,30):
    j = 2
    counter = 0
    while j < i:
        if i % j == 0:
            counter = 1
            j = j + 1
        else:
            j = j + 1

    if counter == 0:
        print(str(i) + " é um número primo")
        counter = 0
    else:
        counter = 0 

Upshot:

2 é um número primo
3 é um número primo
5 é um número primo
7 é um número primo
11 é um número primo
13 é um número primo
17 é um número primo
19 é um número primo
23 é um número primo
29 é um número primo

Is there any way I can see the code working step by step (see the variables assuming the values) so I can understand how the code behaves?

Until the number 3 I believe I understood how it is done, but in the number 4 no. If the j in the previous execution assumed the value of 3 the counter would not change and the number 4 would be considered prime?

Answer 1

To see code working step by step, use a Debugger this link has several options, choose one and use (if you are using IDE’s, like Pycharm for example: they usually already come with a Debugger). Since it’s a relatively small code, you can also do the table test, besides following these tips.

---

What happens when i is equal to 4?

• j receives the amount 2 and counter receives the amount 0
• gets into the while j < i
• if i % j == 0: the operation i % j in this case is 4 % 2 (the rest of the division 4 by 2), which is zero, then enters the if
• within the if, counter receives the amount 1 and j is incremented to 3
• continues to perform the while
• now i % j is 4 % 3, that is 1, then get in the else, that increases j for 4
• as j and i are worth 4, j is not less than i, then closes the while
• counter is worth 1 so does not enter the if counter == 0. He enters the else, that only Zera the counter

Basically, if the number i not cousin, one hour will enter the first if (because there will be some value of j for which the rest of the division will be zero) and will change the value of counter to 1 (indicating that it is not prime). And after the while end, will not enter the second if and therefore will not print the message that the number is prime.

What if i is a prime number, never enters the first if (for the rest of the division will never be zero), then counter will be zero and will enter the second if.

---

But honestly, the code is kind of redundant. For example, within the while, the j is always increasing (both within the if how much in the else), then in fact the increment is something that is always executed, regardless of the case. So it could be executed only once, outside the if/else.

In the second if, the same thing: counter is set to zero in both cases. But in this case it’s even more redundant, because we always reset the counter before the while, then reset the counter there is no need. And in fact, as counter is a variable that indicates only a condition "yes" or "no" (is prime or is not), it could very well be a boolean.

Anyway, a slightly better alternative would be:

for i in range(2, 30):
    j = 2
    primo = True
    while j < i:
        if i % j == 0:
            primo = False
            break
        j = j + 1

    if primo:
        print(f"{i} é um número primo")

Or else:

for i in range(2, 30):
    primo = True
    for j in range(2, i // 2 + 1): # só preciso ir até a metade do número
        if i % j == 0:
            primo = False
            break

    if primo:
        print(f"{i} é um número primo")

Notice I used break, which serves to interrupt the loop (because if I have already discovered that the number is not prime, I don’t need to keep testing, I can stop right there). I also changed the variable name, because counter implies that it is an accountant, but the variable is not counting anything, it only serves to indicate if the number is prime or not. And in the second example, I did the loop up to half of i, for you don’t have to go to i.

Actually, you can do it that way too:

for i in range(2, 30):
    for j in range(2, i // 2 + 1):
        if i % j == 0:
            break
    else:
        print(f"{i} é um número primo")

Yes, in Python one loop may have a block else associated, which shall be executed only if the loop was not interrupted by a break.

Of course you can improve more: with the exception of 2, all the other prime numbers are odd, so I don’t need to test all the numbers; and instead of going to half the number (as done in the second example), I can go to the square root of the same which is already enough, etc, but there already escapes a little from the scope of the question (research, will find many more efficient algorithms to determine if a number is prime).

Answer 2

I solved a task similar to this using while structure, see:

div=2
cont=0
resto=1
while resto!=0:
    if numero<2:
        resto=0
        break
    resto=numero%div
    cont+=1
    div=(2*cont)+1
    if div==numero:
        break
if resto==0 and numero!=2:
    print("Nao e primo")
else:
    print("E numero primo")```