# Problem of prime number counter

Hi, i got a code which prints all prime numbers to infinity. But how does it work with print(w), i thought it must be print(q)?

Please post your code as text, I donâ€™t want to type it over.

2 Likes

I recommend you read through this as it makes helping you easier for others: About the Python Help category

Anyway, Iâ€™ve renamed the values to be more descriptive in your code:

``````potential_prime_squared =  3  # q
potential_prime_divisor = 2  # w

while 0 == 0:  # Why not just use 'True'?
potential_prime = potential_prime_squared ** 0.5  # t

if potential_prime_squared % potential_prime_divisor == 0: # interstingly enough this works because pontential_prime_divisor only reaches (at max.) the value of potential_prime-1 meaning that the square of a prime is not divisible by any number in the range of 2 to prime-1, which I find to be quite interesting, see proof of concept
potential_prime_squared += 1
potential_prime_divisor = 2
else:
potential_prime_divisor += 1
if potential_prime_divisor == potential_prime:
print(potential_prime_divisor)
potential_prime_divisor = 2
potential_prime_squared += 1
``````

So the reason why printing `q` (`potential_prime_squared`) will give a wrong answer is that you are comparing it to the square root of it meaning that the value it holds will be higher and might not even be a prime number.

This also highlights why giving your variables good names is very important as it will be way easier to think through your code, improve it, and understand it again.

Proof of concept:

``````prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 364565471, 364565503]  # I've tested this with a list of 1000 prime_numbers with the same result, so I shortened this list
for prime_number in prime_numbers:
prime_squared = prime_number**2
divisible = False
for i in range(2, prime_number):
if prime_squared % i == 0:
divisible = True
break
print(divisible)
``````

Even more fun fact: a square of a prime can never be a prime as it will always have 3 divisors: 1, the prime itâ€™s the square from, and itself. Other than that it would appear that they are also not divisible by any other values, so tho they are no primes they certainly are kind of special too.

1 Like

While I appreciate that youâ€™re trying to help new users. If you do the work for them, they wonâ€™t learn anything. If theyâ€™re not able to post code as text, we shouldnâ€™t go through the effort of typing it for them.

1 Like

And please donâ€™t use tabs for indentation.

2 Likes

Yeah thatâ€™s true I guess, I just thought Iâ€™ll be nice and just do it anyway, wonâ€™t happen again xD.

Ah sorry, Iâ€™m used to IDEs where tabs are automatically converted to spaces

That is not correct. It is an example of taking a proposition that is true, but the contrapositive of its converse is not.

It is true that if they do the work, then they learn (better). The converse, â€śif they learn, then they do the workâ€ť is false, and so must be the contrapositive of this â€śif they donâ€™t do the work, then they donâ€™t learnâ€ť.

One learns, and can do work on, that which is inside our sphere of understanding and past experiences, or outside it but sufficiently near. Seeing othersâ€™ work is required to increase or even have a collection of past experiences. Renaming variables might be trivial, but the choice of those specific names is not. A more fleshed out idea of what that â€śrenamingâ€ť is doing is the idea of loop invariant, another non-trivial idea that almost everyone learns by seeing others use it, not by discovering it. Even knowing the idea of loop invariants, producing them in each case is not easy.

I wasnâ€™t talking about renaming the variables: I was simply talking about copying the code instead of posting a screenshot.

You could start analyzing the code starting from the â€śendâ€ť, the point where `w` is printed.

For that to happen, the condition `w == t` must be satisfied.

Loop invariant 1: One condition that remains true all the time (it is a loop invariant) is that `w` is an `int` and it is larger than `1`. This is because only `2` gets assigned to it, and we only ever add `1` to it. Being an integer larger than `1` is part of the conditions for being a prime. So, at least we have that covered.

Therefore, for `w == t` to be satisfied, `t` must be equal to an integer.

Note 1: Here you find one of the problems of the code, that it might fail to do what you(it) claim(s). It could be possible that `q` got so large, that the `float` resulting from `q ** 0.5` can only store the information of the integer part of the square root of `q`. Letâ€™s ignore this for the moment.

So, at least for not-so-large `q`, the `w` will get printed, when `q` is a perfect square equal to `t ** 2`.

Now letâ€™s study the loop starting from the first time that `t` is an integer and `q` is `t ** 2`.

Loop invariant 2: Note that another loop invariant is that `q` increases by `1` every time. So, it hits every positive integer starting from `3` and also there is a first time (iteration of the loop) that `q` is `t ** 2`, for any given integer `t`.

Ignoring Note 1, `w` only gets printed when `q` is a perfect square. So, we can focus exclusively on the iterations that `q` is a perfect square.

Loop invariant 3: Another loop invariant is that whenever `q` just got increased, the `w` became `2`. This guarantees the next.

Loop invariant 4: Yet, another loop invariant is that `w` is less than or equal to `t`. Well, this is not true for the very first iteration, but it is true afterwards.

Note 2: Examining the first couple of iterations shows that `2` never gets printed. That is another way in which the code doesnâ€™t exactly do what it claims.

Now. If `t` is not prime, then there is a prime `p`, smaller than `t` that divides it and therefore divides `q`. When `w` hits that value `p`, `q` gets increased and it is no longer equal to `t ** 2` (and `w` gets reset back to `2`). Therefore, `w` gets printed only (under the assumption that `q` is not too large) when `t` is prime and `w == t`.

Every prime `p` (larger than `2`) gets printed, since `q` will be equal to `p ** 2` at some point.

Letâ€™s go back to Note 1, to see if that issue could cause the code to print non-primes.
Suppose that `q` takes a value that is a somewhat large prime, like 2^{257}-1. When Python computes `q ** 0.5` the result is `t = 4.8123193833600906e+38`.
Note that `w` will never divide `q` until `w == q` is satisfied, since `q` is prime and `w` is larger than `1` (Loop invariant 1). Before `w` gets to be equal to `q`, `w` becomes `481231938336009055986162049162441392128`, which is `int(t)`. Then, `w == t` is satisfied, and `w` gets printed. However, this value is not prime (it is even).