Printing out the Sieve of Eratosthenes is the Harder Problem
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).
What caught me by surprise was that even printing out the result on the console became an issue.
As most math majors know, the Sieve simply build 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 start stepping through you candidates, 4, 5, 6, 7, ... one at at a time. 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 candidates grow large, say to 500. 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)
I was so focused on the act of printing out the lines such that there are no more than 25 elements per line that I didn't comprehend the more general challenge; which is ... to generate a "fattened" as opposed to "flattened" list.
In the fattening process, we start with a flattened list (say the list of all primes) and we generate a nested structure composed of plural sub-lists (each 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_sls = len(primes)/25. And the size of the last leftover list is len(prime)%25. This can be implemented as a function that applies to any list, not just one populated by primes.
TO BE CONTINUED
Comments
Post a Comment