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).