I am writing notes for my students under the topic of prime factorization and I needed to illustrate the Sieve of Eratosthenes and this is what I came up with in tikz
:
\documentclass{article}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[scale=0.65]
\draw[very thick,red] (3,9)--(4,10);
\draw[very thick,red] (3,10)--(4,9);
\draw[very thick,red] (5,9)--(6,10);
\draw[very thick,red] (5,10)--(6,9);
\draw[very thick,red] (7,9)--(8,10);
\draw[very thick,red] (7,10)--(8,9);
\draw[very thick,red] (8,9)--(9,10);
\draw[very thick,red] (8,10)--(9,9);
\draw[very thick,red] (9,9)--(10,10);
\draw[very thick,red] (9,10)--(10,9);
%------------------------------------
\draw[very thick,red] (1,8)--(2,9);
\draw[very thick,red] (2,8)--(1,9);
\draw[very thick,red] (3,8)--(4,9);
\draw[very thick,red] (4,8)--(3,9);
\draw[very thick,red] (4,8)--(5,9);
\draw[very thick,red] (5,8)--(4,9);
\draw[very thick,red] (5,8)--(6,9);
\draw[very thick,red] (6,8)--(5,9);
\draw[very thick,red] (7,8)--(8,9);
\draw[very thick,red] (8,8)--(7,9);
\draw[very thick,red] (9,8)--(10,9);
\draw[very thick,red] (10,8)--(9,9);
%------------------------------------
\draw[very thick,red] (0,7)--(1,8);
\draw[very thick,red] (1,7)--(0,8);
\draw[very thick,red] (1,7)--(2,8);
\draw[very thick,red] (2,7)--(1,8);
\draw[very thick,red] (3,7)--(4,8);
\draw[very thick,red] (4,7)--(3,8);
\draw[very thick,red] (4,7)--(5,8);
\draw[very thick,red] (5,7)--(4,8);
\draw[very thick,red] (5,7)--(6,8);
\draw[very thick,red] (6,7)--(5,8);
\draw[very thick,red] (6,7)--(7,8);
\draw[very thick,red] (7,7)--(6,8);
\draw[very thick,red] (7,7)--(8,8);
\draw[very thick,red] (8,7)--(7,8);
\draw[very thick,red] (9,7)--(10,8);
\draw[very thick,red] (10,7)--(9,8);
%------------------------------------
\draw[very thick,red] (1,6)--(2,7);
\draw[very thick,red] (2,6)--(1,7);
\draw[very thick,red] (2,6)--(3,7);
\draw[very thick,red] (3,6)--(2,7);
\draw[very thick,red] (3,6)--(4,7);
\draw[very thick,red] (4,6)--(3,7);
\draw[very thick,red] (4,6)--(5,7);
\draw[very thick,red] (5,6)--(4,7);
\draw[very thick,red] (5,6)--(6,7);
\draw[very thick,red] (6,6)--(5,7);
\draw[very thick,red] (7,6)--(8,7);
\draw[very thick,red] (8,6)--(7,7);
\draw[very thick,red] (8,6)--(9,7);
\draw[very thick,red] (9,6)--(8,7);
\draw[very thick,red] (9,6)--(10,7);
\draw[very thick,red] (10,6)--(9,7);
%------------------------------------
\draw[very thick,red] (1,5)--(2,6);
\draw[very thick,red] (2,5)--(1,6);
\draw[very thick,red] (3,5)--(4,6);
\draw[very thick,red] (4,5)--(3,6);
\draw[very thick,red] (4,5)--(5,6);
\draw[very thick,red] (5,5)--(4,6);
\draw[very thick,red] (5,5)--(6,6);
\draw[very thick,red] (6,5)--(5,6);
\draw[very thick,red] (7,5)--(8,6);
\draw[very thick,red] (8,5)--(7,6);
\draw[very thick,red] (8,5)--(9,6);
\draw[very thick,red] (9,5)--(8,6);
\draw[very thick,red] (9,5)--(10,6);
\draw[very thick,red] (10,5)--(9,6);
%------------------------------------
\draw[very thick,red] (0,4)--(1,5);
\draw[very thick,red] (1,4)--(0,5);
\draw[very thick,red] (1,4)--(2,5);
\draw[very thick,red] (2,4)--(1,5);
\draw[very thick,red] (3,4)--(4,5);
\draw[very thick,red] (4,4)--(3,5);
\draw[very thick,red] (4,4)--(5,5);
\draw[very thick,red] (5,4)--(4,5);
\draw[very thick,red] (5,4)--(6,5);
\draw[very thick,red] (6,4)--(5,5);
\draw[very thick,red] (6,4)--(7,5);
\draw[very thick,red] (7,4)--(6,5);
\draw[very thick,red] (7,4)--(8,5);
\draw[very thick,red] (8,4)--(7,5);
\draw[very thick,red] (9,4)--(10,5);
\draw[very thick,red] (10,4)--(9,5);
%------------------------------------
\draw[very thick,red] (1,3)--(2,4);
\draw[very thick,red] (2,3)--(1,4);
\draw[very thick,red] (2,3)--(3,4);
\draw[very thick,red] (3,3)--(2,4);
\draw[very thick,red] (3,3)--(4,4);
\draw[very thick,red] (4,3)--(3,4);
\draw[very thick,red] (4,3)--(5,4);
\draw[very thick,red] (5,3)--(4,4);
\draw[very thick,red] (5,3)--(6,4);
\draw[very thick,red] (6,3)--(5,4);
\draw[very thick,red] (7,3)--(8,4);
\draw[very thick,red] (8,3)--(7,4);
\draw[very thick,red] (8,3)--(9,4);
\draw[very thick,red] (9,3)--(8,4);
\draw[very thick,red] (9,3)--(10,4);
\draw[very thick,red] (10,3)--(9,4);
%------------------------------------
\draw[very thick,red] (1,2)--(2,3);
\draw[very thick,red] (2,2)--(1,3);
\draw[very thick,red] (3,2)--(4,3);
\draw[very thick,red] (4,2)--(3,3);
\draw[very thick,red] (4,2)--(5,3);
\draw[very thick,red] (5,2)--(4,3);
\draw[very thick,red] (5,2)--(6,3);
\draw[very thick,red] (6,2)--(5,3);
\draw[very thick,red] (6,2)--(7,3);
\draw[very thick,red] (7,2)--(6,3);
\draw[very thick,red] (7,2)--(8,3);
\draw[very thick,red] (8,2)--(7,3);
\draw[very thick,red] (9,2)--(10,3);
\draw[very thick,red] (10,2)--(9,3);
%------------------------------------
\draw[very thick,red] (0,1)--(1,2);
\draw[very thick,red] (1,1)--(0,2);
\draw[very thick,red] (1,1)--(2,2);
\draw[very thick,red] (2,1)--(1,2);
\draw[very thick,red] (3,1)--(4,2);
\draw[very thick,red] (4,1)--(3,2);
\draw[very thick,red] (4,1)--(5,2);
\draw[very thick,red] (5,1)--(4,2);
\draw[very thick,red] (5,1)--(6,2);
\draw[very thick,red] (6,1)--(5,2);
\draw[very thick,red] (6,1)--(7,2);
\draw[very thick,red] (7,1)--(6,2);
\draw[very thick,red] (7,1)--(8,2);
\draw[very thick,red] (8,1)--(7,2);
\draw[very thick,red] (9,1)--(10,2);
\draw[very thick,red] (10,1)--(9,2);
%------------------------------------
\draw[very thick,red] (0,0)--(1,1);
\draw[very thick,red] (1,0)--(0,1);
\draw[very thick,red] (1,0)--(2,1);
\draw[very thick,red] (2,0)--(1,1);
\draw[very thick,red] (2,0)--(3,1);
\draw[very thick,red] (3,0)--(2,1);
\draw[very thick,red] (3,0)--(4,1);
\draw[very thick,red] (4,0)--(3,1);
\draw[very thick,red] (4,0)--(5,1);
\draw[very thick,red] (5,0)--(4,1);
\draw[very thick,red] (5,0)--(6,1);
\draw[very thick,red] (6,0)--(5,1);
\draw[very thick,red] (7,0)--(8,1);
\draw[very thick,red] (8,0)--(7,1);
\draw[very thick,red] (8,0)--(9,1);
\draw[very thick,red] (9,0)--(8,1);
\draw[very thick,red] (9,0)--(10,1);
\draw[very thick,red] (10,0)--(9,1);
%------------------------------------
\draw (0,0) grid (10,10);
\draw (0.5,9.5) node {};
\draw (1.5,9.5) node {2};
\draw (2.5,9.5) node {3};
\draw (3.5,9.5) node {4};
\draw (4.5,9.5) node {5};
\draw (5.5,9.5) node {6};
\draw (6.5,9.5) node {7};
\draw (7.5,9.5) node {8};
\draw (8.5,9.5) node {9};
\draw (9.5,9.5) node {10};
%--------------------------
\draw (0.5,8.5) node {11};
\draw (1.5,8.5) node {12};
\draw (2.5,8.5) node {13};
\draw (3.5,8.5) node {14};
\draw (4.5,8.5) node {15};
\draw (5.5,8.5) node {16};
\draw (6.5,8.5) node {17};
\draw (7.5,8.5) node {18};
\draw (8.5,8.5) node {19};
\draw (9.5,8.5) node {20};
%--------------------------
\draw (0.5,7.5) node {21};
\draw (1.5,7.5) node {22};
\draw (2.5,7.5) node {23};
\draw (3.5,7.5) node {24};
\draw (4.5,7.5) node {25};
\draw (5.5,7.5) node {26};
\draw (6.5,7.5) node {27};
\draw (7.5,7.5) node {28};
\draw (8.5,7.5) node {29};
\draw (9.5,7.5) node {30};
%--------------------------
\draw (0.5,6.5) node {31};
\draw (1.5,6.5) node {32};
\draw (2.5,6.5) node {33};
\draw (3.5,6.5) node {34};
\draw (4.5,6.5) node {35};
\draw (5.5,6.5) node {36};
\draw (6.5,6.5) node {37};
\draw (7.5,6.5) node {38};
\draw (8.5,6.5) node {39};
\draw (9.5,6.5) node {40};
%--------------------------
\draw (0.5,5.5) node {41};
\draw (1.5,5.5) node {42};
\draw (2.5,5.5) node {43};
\draw (3.5,5.5) node {44};
\draw (4.5,5.5) node {45};
\draw (5.5,5.5) node {46};
\draw (6.5,5.5) node {47};
\draw (7.5,5.5) node {48};
\draw (8.5,5.5) node {49};
\draw (9.5,5.5) node {50};
%--------------------------
\draw (0.5,4.5) node {51};
\draw (1.5,4.5) node {52};
\draw (2.5,4.5) node {53};
\draw (3.5,4.5) node {54};
\draw (4.5,4.5) node {55};
\draw (5.5,4.5) node {56};
\draw (6.5,4.5) node {57};
\draw (7.5,4.5) node {58};
\draw (8.5,4.5) node {59};
\draw (9.5,4.5) node {60};
%--------------------------
\draw (0.5,3.5) node {61};
\draw (1.5,3.5) node {62};
\draw (2.5,3.5) node {63};
\draw (3.5,3.5) node {64};
\draw (4.5,3.5) node {65};
\draw (5.5,3.5) node {66};
\draw (6.5,3.5) node {67};
\draw (7.5,3.5) node {68};
\draw (8.5,3.5) node {69};
\draw (9.5,3.5) node {60};
%--------------------------
\draw (0.5,2.5) node {71};
\draw (1.5,2.5) node {72};
\draw (2.5,2.5) node {73};
\draw (3.5,2.5) node {74};
\draw (4.5,2.5) node {75};
\draw (5.5,2.5) node {76};
\draw (6.5,2.5) node {77};
\draw (7.5,2.5) node {78};
\draw (8.5,2.5) node {79};
\draw (9.5,2.5) node {80};
%--------------------------
\draw (0.5,1.5) node {81};
\draw (1.5,1.5) node {82};
\draw (2.5,1.5) node {83};
\draw (3.5,1.5) node {84};
\draw (4.5,1.5) node {85};
\draw (5.5,1.5) node {86};
\draw (6.5,1.5) node {87};
\draw (7.5,1.5) node {88};
\draw (8.5,1.5) node {89};
\draw (9.5,1.5) node {90};
%--------------------------
\draw (0.5,0.5) node {91};
\draw (1.5,0.5) node {92};
\draw (2.5,0.5) node {93};
\draw (3.5,0.5) node {94};
\draw (4.5,0.5) node {95};
\draw (5.5,0.5) node {96};
\draw (6.5,0.5) node {97};
\draw (7.5,0.5) node {98};
\draw (8.5,0.5) node {99};
\draw (9.5,0.5) node {100};
\end{tikzpicture}
\end{document}
This is what results:
Evidently it is not the most suitable way and it took me a while to get it right. I know there is a less tedious way of doing it but for the moment this is what I have to deal with. If anyone can assist me with the matter I would appreciate it. Something tells me that a \foreach
would suffice but I still don't know its implementation.
Best Answer
As others have pointed out the static output showing the final results (even with different shadings and colors) still looks like a table of primes. Well, then the only way to properly show this is to use animations.
This uses the actual Sieve of Eratosthenes algorithm to highlight each multiple of
2
in red to mark it as non-prime. Then, the next unmarked number is prime, and its multiples are marked as non-prime. The darker the shade of red indicates the higher number of times that number got marked as non-prime (i.e., has a higher number of prime factors). At each step, the newly found prime is highlighted in blue, and the list of current primes is shown.Animated Version:
The PDF animation can be produced with the following settings:
For a 10x10 use (See Further Enhancements section below regarding
\FramesToHoldAtEnd
):Note that this requires a PDF viewer capable of showing animations (such as Acrobat).
A gif animation can also be produced:
The above animation used the following settings:
and post-processed as per Converting beamer slides to animated images:
This also necessitated scaling of the
tikzpicture
to get a reasonable sized gif for display here, and hence this looks slightly different than the others.Paper Version: Step-by-Step
But this raises the question: But what if I want to show the steps on paper? Well, then with the settings below you get a step-by-step approach.
Paper Version: Final Table
To obtain just the final table for a 10x10, use the settings:
Non-square sizes can be produced as well by adjusting the value of
\NumOfColumns
and\NumOfRows
:Questions:
Question 1
andQuestion 2
. If I don't figure them out, I will post new questions.Notes:
Further Enhancements:
The
\FramesToHoldAtEnd
must be large enough to find all the remaining primes. The default settting of25
is enough for 10x10 but this could be automated to add additional frames until all the primes were found in case this was not set to be large enough.Each individual step takes the same amount of time. For a 10x10, there are 50 multiples of 2 to eliminate, and only 20 for multiples of 5. Instead of each step taking the same amount of time, could adjust it so that an entire list of multiples are processed in the same amount of time. So, for example, the 50 multiples of 2 are highlighted in 3 seconds, and the 20 multiples of 3 are also highlighted in 3 seconds.
Code: