Printing out the Sieve of Eratosthenes is the Harder Problem

October 04, 2025

As mentioned in the preceding post (here), you learn by doing. And especially by making mistakes!

While working on understanding list comprehensions, it came to my mind that perhaps I could apply it to The Sieve of Eratosthenes.

I can't say that I figured out how to implement the Sieve with list comprehensions (at least not yet, but see below re my fatten() function).

What caught me by surprise was that even printing out the result on the console became an issue due to the length of the resulting list produced by the Sieve algorithm.

As most math majors know, the Sieve simply builds up a list of primes by trying to divide each successive candidate integer by all of the previously found primes. You create a seed list of primes, say [2, 3] and then you start stepping through further candidates, 4, 5, 6, 7, ... one at at a time. For example, 4 is divisible by the already known prime,2; so 4 fails as a valid candidate. 5 passes though and gets appended to the primes list. Same goes for 7, 11 and so on.

So what happens if you let the list of possible candidates grow large, say to 500 or beyond? One console line cannot neatly hold all the found primes.

Below is a screen capture of what I ultimately developed. (The fail safe count was there to prevent a never ending loop. More on that later): (Left click on image to enlarge)

As can be seen, I found a way to break up the output list inot a bunch of shorter sub-lists. I was so focused on the act of printing out these lines of no more than 25 elements per line that I failed to recognize the more generalized challenge; namely, creating a function that generates a "fattened" list as opposed to a "flattened" list. (See here and here for more re flattening of nested lists)

In the converse "fattening" process, we start with a flattened list (say the list of all primes, herein also our "skinny" list). We then generate a nested structure composed of plural sub-lists (say each being 25 elements long) inside the main list. So it would look something like this: primes_nested = [ [0, 1, 2, 3, 4, ...24], [ 25, ...., 49], [50, ...], ... [leftover last set] ]

We can do simple math to figure out how many sub-lists we will need: N_of_sublists = len(primes)/25. To strip off the fraction in the answer, use the int() function. (See here for more W3 on built-in functions) For the size of the last, leftover sub list, we use the modulus operator. In other words, R= len(primes)%25. (See also here and here) This can be implemented as a function that applies to any skinny list, not just one populated by primes.

The below fatten() function is implemented with a nested list comprehension that accounts for the fact that indexing starts at zero (0) and not 1. More specifically, see lines 69-73 o f the third image below (click on it to enlarge) One thing I didn't yet do is extend() the output to account for the last, leftover substring. That is forthcoming ...

Below is output from nested comprehensions: (click to enlarge)

Here is the code that makes the function calls:

And here are some of the called functions including the fatten() function:

Post Script:
I finally added the remainder handling code to the fatten() function
Some funny business came up
First, I couldn't do a straight forward walk from -R to -1 inclusive. Instead, I has to start at -1 and walk back wards to -R inclusive, Then, reverse that result.
[[ Post script: Above statement is error. The way to walk forward all the way to index -1 inclusive is this: partial_end_list = full[plus_index::] where plus_index is the positive recitation of -R, in other words, =len(full)-R ]]
Second, I couldn't use the extend() method because it take elements out of the sublist, Instead, I had to use append() AND put remainder inside an extra pair of sq brackets. Don't yet understand why that is so. But now it works as shown in the next three succeeding images (Scratch_01 code, Funcs_01 code, Console output --click on each to enlarge):