List comprehensions without filter

Question

Recently came across this piece of code online:

nonprime = [j for i in range(2, 8) for j in range(i*2, 50, i)]

The above code seems to be calculating all the non primes below 50,but I am not getting the logic. I studied list comprehensions in python and observed it uses filter to filter based on conditions, but all I cannot understand how two for loops are calculating these non primes.

Answer 1

This list comprehension does the same as these two nested for loops:

nonprime=[]
for i in range(2,8):
    for j in range(i*2, 50,i):
        nonprime.append(j)

So in the outer loop, i is just increased by one in every iteration, and takes on the values i=2,3,4,5,6,7. The inner for loop over j depends on the outer loop. It starts at 2*i and j is increased by i in each iteration.

So for ì=2, the inner loop starts at j=4 and j takes on the values j=4,6,8,...,48. Then ì is increased to 3 in the outer loop and j takes on the values 6,9,12,...48

Notice that the nonprime list does not create unique elements, since for example the 6 appears more than once.

As Bakuriu rightfully points out, this method makes use of the Sieve of Eratosthenes

Answer 2

The key to this answer lies in Mathematics:

If a number n>1 is not prime, then it has a prime factor <= sqr(n)

Now we are left to explain the logic. Note that sqrt(50) < 8, which is the limit of the first range.

We may rewrite the nested list comprehension as a regular loop. We can use set instead of a list, which will have unnecessary repeated elements:

res = set()

for i in range(2, 8):
    for j in range(i*2, 50, i):
        res.add(j)

The outer loop iterates all i < sqrt(50).

The inner loop iterates, for each i, all multiples of i less than 50.

By the aforementioned Mathematical statement, we have all non-primes under 50. This is true because we are exhausting all prime factors <= sqrt(50).