I wrote a simple python module that returns the prime numbers up to a given N, using a bool flag is_prime as follows:
def generate_primes_up_to(M):
n = 2
primes = []
while n <= M:
is_prime = True
for p in primes:
if p**2 > n: break
if n % p == 0:
is_prime = False
break
if is_prime: primes.append(n)
n += 1
return primes
if __name__ == '__main__':
generate_primes_up_to(100)
which outputs:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Now, this is actually an ideal case for using the for-else construct, since the number n is prime only if no breaks occurred in the for loop. Thus, I changed the function into:
def generate_primes_up_to(M, flag='nonumpy'):
n = 2
primes = []
while n <= M:
for p in primes:
if p**2 > n: break
if n % p == 0: break
else: primes.append(n)
n += 1
return primes
but now the code outputs:
[2, 5, 27]
I don't understand why the if p**2 > n: break expression is interfering with the flow of the for-else clause. If I remove that line the code yields the right output again.
The condition causing the issue is -
if p**2 > n: break
Lets take an example - 7 , when we are checking if 7 is prime or not , we have already found out that - [2,3,5] are primes, the above condition breaks the for loop, when we check 3 as 3**2 = 9 which is greater than 7 .
Remove that condition and it works fine (Though its very slow).
In the original loop (without the for-else construct) , it worked because in that condition you just broke out of the loop, you did not change the flag is_prime .
With the for..else construct, what happens is that, the else part is only executed when we exit the loop without using break statement.
But in the case of the above condition , we use break statement and hence else part is not executed.