For-Else Statement with Multiple If-Break Conditions

Question

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.

Answer 1

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.

Answer 2

You can also use next:

def generate_primes_up_to(M):
    n = 2
    primes = []
    while n <= M:
        if next((False for p in primes if not n % p), True):
            primes.append(n)
        n += 1

    return primes