Sieve of Eratosthenes in tikz
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:
%\def\ShowStepByStep{}% Ignored in this case
\def\AnimateSieve{}%
%\def\AnimatedGif{}% Must be commented
For a 10x10 use (See Further Enhancements section below regarding \FramesToHoldAtEnd):
\def\NumOfColumns{10}%
\def\NumOfRows{10}%
\def\FramesToHoldAtEnd{25}% 25 is enough for 10x10
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:
%\def\ShowStepByStep{}% Ignored in this case
%\def\AnimateSieve{}% Ignored in this case
\def\AnimatedGif{}%
\def\NumOfColumns{5}%
\def\NumOfRows{5}%
\def\FramesToHoldAtEnd{10}%
and post-processed as per Converting beamer slides to animated images:
pdfcrop SieveOfEratosthenesAnimated.pdf
convert -verbose -delay 100 -loop 0 -density 400 SieveOfEratosthenesAnimated-crop.pdf SieveOfEratosthenesAnimated.gif
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.
\def\ShowStepByStep{}%
%\def\AnimateSieve{}% This MUST be commented
%\def\AnimatedGif{}% This MUST be commented
\def\NumOfColumns{7}%
\def\NumOfRows{7}%
\def\FramesToHoldAtEnd{10}%
Paper Version: Final Table
To obtain just the final table for a 10x10, use the settings:
%\def\ShowStepByStep{}% ALL of these must be commented
%\def\AnimateSieve{}%
%\def\AnimatedGif{}%
\def\NumOfColumns{10}%
\def\NumOfRows{10}%
\def\FramesToHoldAtEnd{25}% 25 is enough for 10x10
Non-square sizes can be produced as well by adjusting the value of \NumOfColumns and \NumOfRows:
Questions:
- There are two places where there might be some code clean up (or at least clear up some confusion on my end as to why what I expected did not work). These are marked as
Question 1andQuestion 2. If I don't figure them out, I will post new questions.
Notes:
- The shading is done on the background layer so that the numbers do not get obscured.
- This is my very first attempt at animations within LaTeX so might not be the most efficient method, so probably has much room for improvement.
Further Enhancements:
The
\FramesToHoldAtEndmust be large enough to find all the remaining primes. The default settting of25is 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:
%%% Sieve of Eratosthenes
%%% ---------------------
%%%
%%% Step 1: Create a list of consecutive integers 2...n
%%% Step 2: Let p=2 be the first prime number
%%% Step 3: Mark multiples of p as non-prime.
%%% Step 4: First number > p not marked as non-prime is prime.
%%% Step 5: Repeat from Step 3 with this new prime.
%%%
%%% ---------------------------------------------------------------
%%% Set-up: Choose desired output:
%%% 1. Animation: GIF, or PDF
%%% 2. Paper version: Step by step) or Final state.
%%%
%\def\ShowStepByStep{}% Comment out if only want final result
%%% Choose if want animated version. This overrides \ShowStepByStep
\def\AnimateSieve{}% Comment out if don't want animated version
%%% Chose if want animated gif image instead. Overrides \AnimateSieve
%\def\AnimatedGif{}%
%
%%% The \AnimatedGif option produces a PDF with each page containing
%%% a single frame. To convert this to a GIF, use the following, where
%%% convert is part of ImageMagik
%%%
%%% pdfcrop SieveOfEratosthenes.pdf
%%% convert -verbose -delay 100 -loop 0 -density 400
%%% SieveOfEratosthenes-crop.pdf
%%% SieveOfEratosthenes.gif
%%% ---------------------------------------------------------------
%%% Customize: Choose size: NumberOfColumns x NumberOfRows
%%% Other options may need tweaking based on size settings
%%%
%%% Note that if the product of \NumOfColumns x \NumOfRows
%%% is greater than 100, the \FramesToHoldAtEnd should be
%%% larger than 25. No check below is made of this, but will
%%% result in some of larger primes not being highlighted at
%%% the end of the cycle (if this is not large enough).
\def\NumOfColumns{10}% See note above if product of
\def\NumOfRows{10}% NumOfColumns and NumOfRows > 100.
%% \FramesToHoldAtEnd should be larger than the number of primes
%% so that they can get highlighted at the end of the process
\def\FrameRate{1}%
\def\FramesToHoldAtStart{3}%
\def\FramesToHoldAtEnd{25}% 25 is enough for 10x10
\def\Scale{0.6}% May need tweaking..
\def\MinipageScale{1.0}%
\def\MinipageScaleForStepByStep{0.49}%
%% Without this scale adjustment for the animated GIF, the image is quite large.
\def\ScaleForAnimatedGif{0.6}%
\def\PrimeColor{yellow}% Shade for primes found previously
\def\NewPrimeColor{cyan}% Shade for prime just found
\def\NewPrimeText{blue}% Color for primes in list
\def\NonPrimeColor{red}% Shade for non-primes
%% List of Primes is typeset into a \node of this width.
\def\TextWidth{2.0cm}%
%%% ---------------------------------------------------------------
\ifdefined\AnimatedGif
\documentclass[border=2pt,multi=true]{standalone}
\else\ifdefined\AnimateSieve
\documentclass{article}
\else
\documentclass{article}% for paper version
\fi\fi
%%% Can use the following to show the final state for large
%%% (tested up to 53x52)
%\usepackage[paperwidth=35in,paperheight=35in]{geometry}
\usepackage{geometry}
\usepackage{microtype}% Allow comma into margin in list of primes
\usepackage{xstring}% String comparison
\usepackage{tikz}% Drawing
\usetikzlibrary{calc}% Coordinate calculations
\usetikzlibrary{backgrounds}% Apply shading on background layer
\ifdefined\AnimatedGif
\usepackage{animate}% no controls, or looping needed
\def\AnimateSieve{}% Simplifies code if this is set for \AnimatedGif as well.
\def\Scale{\ScaleForAnimatedGif}% Otherwise GIF is too large
% Simplifies code below if we just redefine these two from the
% animate package so that they do don't much.
\renewenvironment{animateinline}[1]{\begingroup}{\endgroup}%
\renewcommand{\newframe}[1][]{\newpage}%
\else% Note: This \else is skipped for \AnimatedGif
\ifdefined\AnimateSieve%
\usepackage[loop,controls]{animate}% looped animation
\let\ShowStepByStep\relax% Ensure that \ShowStepByStep is undefined
\else% Print version
\usepackage{animate}% provides whiledo (could include ifthen)
% Simplifies code below if we just redefine these two from the
% animate package so that they do don't much.
\renewenvironment{animateinline}[1]{\begingroup}{\endgroup}%
\renewcommand{\newframe}[1][]{\newpage}%
\ifdefined\ShowStepByStep
\def\MinipageScale{\MinipageScaleForStepByStep}%
\fi
\fi
\fi
%%% ---------------------------------------------------------------
%%% Should not need to adjust anything below this line
%%%
\pgfmathtruncatemacro{\MaxNumber}{\NumOfRows*\NumOfColumns}%
\pgfmathtruncatemacro{\MaxValue}{sqrt(\MaxNumber)}%
% Choose opacity so that we can have the max number of shades
\pgfmathsetmacro{\Opacity}{1.0/min(20,\MaxValue-1)}%
%% The Sieve algorithm requires that once a number is marked
%% as non-prime (i.e., was a multiple of some other number)
%% we don't need to check multiples of that number as they
%% have already been marked as non-prime.
%%
%% Usually one would use an array and set a flag. But since
%% variables with numbers are difficult with TeX, we can
%% define a node named with the number that is non-prime.
%% Then just check that the node exists to see if it was
%% marked as non-prime.
\makeatletter
% Mark number as either "Prime" or "NonPrime".
\newcommand*{\MarkNumber}[2][NonPrime]{\node (#1#2) {}}% #1=prefix, #2=num
% https://tex.stackexchange.com/questions/37709/how-can-i-know-if-a-node-is-already-defined
\newcommand{\IfNumberAlreadyMarked}[4][NonPrime]{% #1=prefix, #2=num
\pgfutil@ifundefined{pgf@sh@ns@#1#2}{#4}{#3}%
}
% https://tex.stackexchange.com/questions/20655/how-to-undo-a-def-i-e-need-a-undef-capability
\newcommand*\@nameundef[1]{%
\global\expandafter\let\csname #1\endcsname\@undefined%
}
%% Since we repeat the process from the beginning for the animated
%% version, use this to clear the nodes so that the numbers are
%% not marked as multiples of a number from the previous run.
\newcommand{\ClearAllNumberedNodeNames}{%
\foreach \i in {1,...,\MaxValue}{%
\@nameundef{pgf@sh@ns@NonPrime\i}%
\@nameundef{pgf@sh@ns@Prime\i}%
}%
}
\makeatother
%% The Sieve algorithm skips multiples of numbers already marked as
%% non-prime. So, to number the individual steps, need to use
%% a counter.
%% i.e., Step 4 is processing multiples of 5 (since we skip 4).
\newcounter{StepNumber}%
%%% ---------------------------------------------------------------
%%%
%%% Titles and Labels
%%%
\newcommand\ListOfPrimes{}
\newcommand\AddToListOfPrimes[2][fill=\PrimeColor]{%
\IfStrEq{\ListOfPrimes}{}{%
\def\Separator{}% First member of list of primes
}{%
\def\Separator{, }% Subsequent member of list of primes
}%
%
\FillCellForGivenNumber[#1]{#2};%
\global\edef\ListOfPrimes{\ListOfPrimes\Separator#2}%
\MarkNumber[Prime]{#2};%
}
\newcommand*{\ClearListOfPrimes}{%
\ClearAllNumberedNodeNames;%
\renewcommand{\ListOfPrimes}{}%
}
\newcommand*{\Title}{%
{\noindent\Large%
\textbf{Sieve of Eratosthenes}~%
($\NumOfColumns \times \NumOfRows$)%
}%
}
\newcommand*{\SubTitleInitial}{%
\noindent\textbf{Step \theStepNumber}: Numbers from 2 \ldots\MaxNumber%
}%
\newcommand*{\SubTitle}[1]{% For animation
\noindent\textbf{Step \theStepNumber}:~%
Eliminating multiples of \textcolor{\NewPrimeText}{\textbf{#1}}%
}
\newcommand*{\SubTitlePastTense}[1]{% For step by step
\noindent\textbf{Step \theStepNumber}:~%
Eliminated multiples of \textcolor{\NewPrimeText}{\textbf{#1}}%
}
\newcommand*{\SubTitleFinal}{%
\IfEq{\the\value{StepNumber}}{0}{%
% We are only showing the final result, so no steps to label.
% This is when we are not animating (nor showing step by step)
}{%
\noindent\textbf{Step \theStepNumber}: Remaining are prime.%
}%
}
\newcommand*{\AddTitleNode}{%
\ifdefined\AnimateSieve% Otherwise don't need title each time
\node [above, yshift=1.0ex] at ($(0,0)!0.5!(\NumOfColumns,0)$) {\Title}
\fi%
}
\newcommand*{\AddSubTitleNode}[1]{%
\IfStrEq{#1}{\empty}{%
% This is the final hold frame where we are showing the primes
\node [right] at (-1,0) {\SubTitleFinal}
}{%
\ifdefined\AnimateSieve%
\node at ($(0,0)!0.5!(\NumOfColumns,0)$) {\SubTitle{#1}}
\else%
\node [right] at (-1,0) {\SubTitlePastTense{#1}}
\fi%
}%
}
\newcommand*{\AddInitialSubTitleNode}[1]{%
\ifdefined\AnimateSieve%
\node at ($(0,0)!0.5!(\NumOfColumns,0)$) {\SubTitleInitial}
\else%
\node [right] at (-1,0) {\SubTitleInitial}
\fi%
}
\newcommand*{\Phantom}[1]{}%
\newcommand*{\ShowListOfPrimesNode}{%
\IfStrEq{\ListOfPrimes}{}{%
%% Empty list of primes, so don't want to show anything.
%% Just add phantom spacing
\renewcommand*{\Phantom}[1]{\phantom{##1}}%
}{%
\renewcommand*{\Phantom}[1]{##1}%
}%
\node [below right, xshift=0.5em, yshift=-0.5ex, align=left, text width=\TextWidth]
at (\NumOfColumns,-1)
{\Phantom{\textbf{Primes:}}};
\node [below right, xshift=0.2em, yshift=-3.5ex, align=left, text width=\TextWidth]
at (\NumOfColumns,-1)
{\Phantom{\textbf{\textcolor{\NewPrimeText}{\raggedleft\ListOfPrimes}}}};
}
%%% ---------------------------------------------------------------
%%%
%%% Step 1: Create a list of integers 2...n
%%%
\newcommand*{\DrawGridWithNumbers}{%
\begin{scope}[draw=gray, thick]% Add numbers to each node
\draw (0,-1) -- ($(0,-\NumOfRows-1)$);
\foreach \col in {1,...,\NumOfColumns} {%
\draw (\col,-1) -- ($(\col,-\NumOfRows-1)$);
\draw (0,-1) -- (\NumOfColumns,-1);
\foreach \row in {1,...,\NumOfRows}{%
\pgfmathtruncatemacro{\value}{\col+\NumOfColumns*(\row-1)}
\IfEq{\value}{1}{
%% Suppress number 1 from being printed since first
%% step of Sieve of Eratosthenes algorithm is to
%% create a list of integers 2...n
}{
\node at ($(\col,-\row)-(0.5,0.5)$) {\textbf{\value}};
}
\draw (0,-\row-1) -- (\NumOfColumns,-\row-1);
}
}
\end{scope}
%% Since we just drew the grid we should ensure that none
%% of the numbered nodes exist (i.e., that no numbers
%% are marked as non-prime. And reset list of primes.
\ClearListOfPrimes;
\ClearAllNumberedNodeNames;
\ShowListOfPrimesNode;
}
\newcommand*{\FillCellForGivenNumber}[2][]{%
%% #1 = fill options
%% #2 = number
%%
\pgfmathtruncatemacro{\Column}{mod(#2,\NumOfColumns)}%
\IfEq{\Column}{0}{\pgfmathtruncatemacro{\Column}{\NumOfColumns}}{}%
\pgfmathtruncatemacro{\Row}{(#2-1)/\NumOfColumns+1}%
\begin{scope}[on background layer]
\fill [#1]
(\Column-1,-\Row) --
($(\Column-1,-\Row)+(1,0)$) --
($(\Column-1,-\Row)+(1,-1)$) --
(\Column-1,-\Row-1) --
cycle;
\end{scope}
}
\newcommand*{\ColorMultiplesOf}[2][0]{%
%% If only 1 arg is given (i.e., #1=0), then
%% #2 = the multiple for which the coloring is applied
%%
%% If two args are given (i.e., #1 != 0) then
%% #1 = Value of \MaxMultiple (used for animated version)
%% In the two arg case we run the entire sequence
%% from the beginning up until the multiple #1*#2
%% is reached.
\IfEq{#1}{0}{% Run the entire sequence
\pgfmathtruncatemacro{\MaxMultiple}{\MaxNumber/#2}
}{% Run sequence up until number given for animating
\def\MaxMultiple{#1}
}
\foreach \i in {2,...,\MaxMultiple} {
\pgfmathtruncatemacro{\NonPrimeNumber}{\i*#2}
\FillCellForGivenNumber[
fill=\NonPrimeColor,
fill opacity=\Opacity
]
{\NonPrimeNumber};
\MarkNumber[NonPrime]{\NonPrimeNumber};
}
}
\newcommand*{\BuildFrameInternals}[2][0]{%
%% #1 = current multiple to which to build the pattern up to
%% if #1=0 and #2=\MaxValue, then we are in an end hold frame
%% #2 = number of whose multiples we are eliminating in this step
%% if #2=1, then only draw grid (provides hold frame at start)
\AddTitleNode;% Print Main title if \AnimateSieve is defined
\DrawGridWithNumbers;
\IfEq{#2}{1}{%
%% This is a hold frame at start so only show grid of numbers
\AddInitialSubTitleNode{#2};
}{%
\IfEq{#2}{2}{%
%% No pre-processing steps to be done in this case
}{%
%% Since we are eliminating multiples of a number
%% other than 2, we need to get the table up to
%% the state where all the multiples of 2...(#2-1)
%% are eliminated.
\pgfmathsetmacro{\PreviousMultiple}{#2 - 1}%
\foreach \n in {2,...,\PreviousMultiple} {%
\IfNumberAlreadyMarked[NonPrime]{\n}{%
%% Skip. Multiples are already marked as non-prime
%% since this number is a multiple of a smaller
%% prime.
}{%
%% This is a prime. Mark it as prime, and mark
%% its multiples as non-prime.
\AddToListOfPrimes[fill=\PrimeColor]{\n};
\ColorMultiplesOf{\n};
}
}
}
\IfNumberAlreadyMarked[NonPrime]{#2}{%
%% Already taken care of in a previous run. This test
%% is needed to cover the case where the value of the
%% sqrt{NumberOfColumns x NumberOfRows) is not prime.
%% For example: 10x10.
}{%
%% Now eliminate the numbers up to the current state
\AddToListOfPrimes[fill=\NewPrimeColor]{#2};
\ColorMultiplesOf[#1]{#2};
}
%% If we are holding the very final result don't print title.
%% This is the case when #2=\MaxValue and #1=0.
%%
%% Need to do this at the end so that we can access
%% which numbers have been marked as non-prime.
\IfEq{#2}{\MaxValue}{%
\IfEq{#1}{0}{%
%% This is the final hold frame
\SubTitleFinal;
\IfNumberAlreadyMarked[NonPrime]{#2}{%
}{%
\IfNumberAlreadyMarked[Prime]{#2}{%
%% In this case, #2 is not a new prime so
%% correct its color. So, don't add it to the
%% list of primes, but correct ensure its
%% color corresponds to an old prime
\FillCellForGivenNumber[fill=\PrimeColor]{#2};
}{%
%% In this case, #2 is a new prime so
%% add it to the list of primes,
\AddToListOfPrimes[fill=\NewPrimeColor]{#2};
}%
}%
%% But since this is the final hold frame, we need
%% to mark all the numbers not already marked as
%% non-prime as prime. Do one at at time, so that
%% this can be seen in the animation.
\pgfmathtruncatemacro{\StartValue}{\MaxValue+1}%
\foreach \p in {\StartValue,...,\MaxNumber}{%
\IfNumberAlreadyMarked[NonPrime]{\p}{%
%% This number has been marked as non-prime
}{%
%% This is a prime
\IfNumberAlreadyMarked[Prime]{\p}{%
%% Already found this prime earlier.
%% So ensure it has appropriate fill.
\AddToListOfPrimes[fill=\PrimeColor]{\p};%
}{%
%% New prime: Mark it as such, and
%% break out to complete this frame.
\AddToListOfPrimes[fill=\NewPrimeColor]{\p};%
\MarkNumber[Prime]{\p};%
\AddSubTitleNode{};%
\breakforeach;%
}%
}%
}%
}{%
%% Not final hold frame, so normal title
\AddSubTitleNode{#2};%
}%
}{%
\AddSubTitleNode{#2};%
}%
}%
\ShowListOfPrimesNode%
}%
\newcommand*{\AddVerticalSpearationForStepByStep}{%
\ifdefined\ShowStepByStep% So that the minipages for this case
\vspace*{4.0ex}% are not stacked directly on top of
\fi% each other.
}%
\newcommand*{\BuildFrame}[2][0]{%
%% #1 = current multiple to which to build the pattern up to
%% #2 = number of whose multiples we are eliminating in this step
%% if #2=1, then only draw grid (provides hold frame at start)
\noindent%
\begin{minipage}{\MinipageScale\linewidth}%
\centering%
\begin{tikzpicture}[scale=\Scale]%
\BuildFrameInternals[#1]{#2};
\end{tikzpicture}%
%
\AddVerticalSpearationForStepByStep% Better spacing for Step by Step
\end{minipage}%
}%
\newcommand*{\BuildFinalFrame}{%
\noindent%
\begin{minipage}{\MinipageScale\linewidth}%
\centering%
\begin{tikzpicture}[scale=\Scale]%
\AddTitleNode;% Print Main title if \AnimateSieve is defined
\AddSubTitleNode{};
\DrawGridWithNumbers;
\foreach \p in {2,...,\MaxValue}{%
\IfNumberAlreadyMarked[NonPrime]{\p}{%
}{%
\AddToListOfPrimes[fill=\PrimeColor]{\p};
\ColorMultiplesOf{\p};
}%
}%
\pgfmathtruncatemacro{\StartValue}{\MaxValue+1}%
\foreach \p in {\StartValue,...,\MaxNumber}{%
\IfNumberAlreadyMarked[NonPrime]{\p}{%
%% This number has already been marked as non-prime
}{%
%% This is a prime. Since we are just printing out
%% the final results we don't distinguish between a
%% newly found prime and a prime found previously.
\AddToListOfPrimes[fill=\PrimeColor]{\p};
}%
}%
\ShowListOfPrimesNode;
\end{tikzpicture}%
%
\AddVerticalSpearationForStepByStep% Better spacing for Step by Step
\end{minipage}%
}
\begin{document}
\ifdefined\AnimateSieve
\newcounter{CountK}
\newcounter{CountP}
\newcounter{CurrentMaxMultiplePlusOne}
%
\begin{animateinline}{\FrameRate}%
\stepcounter{StepNumber}%
\setcounter{CountK}{0}%
\whiledo{\arabic{CountK} < \FramesToHoldAtStart}{%
\BuildFrame[0]{1}% initial hold frame
\newframe[\FrameRate]%
\stepcounter{CountK}%
}%
%
\setcounter{CountK}{2}%
\whiledo{\numexpr\arabic{CountK}-1 < \MaxValue}{%
\IfNumberAlreadyMarked[NonPrime]{\arabic{CountK}}{%
%% \value{CountK} has already been marked as non-prime.
%% Hence, so so are its multiples, and we can skip it.
}{%
%% Question 1: Should be able to replace three lines following with
%% this. But then animation seems to skip the loop below
% \pgfmathsetcounter{CurrentMaxMultiplePlusOne}{1+(\MaxNumber/\arabic{CountK})}%
\pgfmathtruncatemacro{\MaxMultiple}{\MaxNumber/\arabic{CountK}}%
\setcounter{CurrentMaxMultiplePlusOne}{\MaxMultiple}%
\stepcounter{CurrentMaxMultiplePlusOne}%
%
\setcounter{CountP}{2}%
\stepcounter{StepNumber}%
%% Question 2: Ideally would prefer to use the following syntax
%% but this does not even compile!!! But, an indentical
%% syntax works in the above `\whiledo`, where the value of
%% \MaxValue was also defined by \pgfmathtruncatemacro
% \whiledo{\numexpr\arabic{CountP}-1 < \MaxMultiple}{%
\whiledo{\arabic{CountP} < \arabic{CurrentMaxMultiplePlusOne}}{%
\BuildFrame[\theCountP]{\theCountK}%
\newframe[\FrameRate]%
\stepcounter{CountP}%
}%
}%
\stepcounter{CountK}%
}%
% At end, add hold frames in case we are looping
%
% There needs to be enough of these so that each of the
% primes (those not colored in) get highlighted at each frame.
%
\setcounter{CountK}{2}%
\whiledo{\numexpr\arabic{CountK}-1 < \FramesToHoldAtEnd}{%
\BuildFrame{\MaxValue}%
\newframe[\FrameRate]%
\stepcounter{CountK}%
}
\end{animateinline}%
\else\ifdefined\ShowStepByStep
\parbox{0.95\linewidth}{\centering\Title\newline}%
\bigskip\par%
\setcounter{StepNumber}{1}%
\BuildFrame[0]{1}% Initial frame
\hfill%
%
\foreach \k in {2,...,\MaxValue}{%
\IfNumberAlreadyMarked[NonPrime]{\k}{%
% \k has already been marked as non-prime.
% Hence, so so are its multiples, and we can skip it.
}{%
% This is a prime, so mark it as such and mark all the
% multiples up to \MaxMultipleOfK as non-prime
\stepcounter{StepNumber}%
\pgfmathtruncatemacro{\MaxMultipleOfK}{\MaxNumber/\k}%
\BuildFrame[\MaxMultipleOfK]{\k}%
\hfill%
}%
}%
%
\stepcounter{StepNumber}%
\BuildFinalFrame% Final Frame
\else% We only want to show the final frame
\parbox{0.95\linewidth}{\centering\Title}
\setcounter{StepNumber}{0}
\par
\BuildFinalFrame%
\fi% \ifdefined\ShowStepByStep
\fi% \ifdefined\AnimateSieve
\end{document}
Here is a shaded polygon-based approach.
(Click image below for 2x larger version.)
\documentclass{article}
\usepackage[margin=1in]{geometry}
\pagestyle{empty}
\usepackage{tikz}
\usepackage{ifthen}
\newcommand{\setxy}[1]{
\pgfmathtruncatemacro{\x}{Mod(#1,\cols)}
\pgfmathtruncatemacro{\y}{#1 / \cols}
\pgfmathtruncatemacro{\y}{\cols - 1 - \y}
\pgfmathparse{2.5*(\x+.5)}\let\x\pgfmathresult
\pgfmathparse{2.5*(\y+.5)}\let\y\pgfmathresult
}
\newcommand{\polygon}[2]{
\setxy{#1}
\ifthenelse{#2>1}{ % Polygon must have at least 2 sides.
\ifthenelse{#2<20}{ % Draw polygon if it has a small number of sides.
\filldraw (\x,\y) +(90:1)
\foreach \i in {1,...,#2} {-- +(\i/#2*360+90:1)} -- cycle;
}{ % Else approximate with circle.
\filldraw (\x,\y) circle(1);
}
}{}
}
\newcommand{\numlabel}[1]{
\setxy{\n}
% Simulate a white outline around the black text.
\foreach \xs in {-.5,-.25,0,.25,.5} {
\foreach \ys in {-.5,-.25,0,.25,.5} {
\node[fill=none, opacity=.25, text=black!10!white,
xshift=\xs, yshift=\ys] at (\x,\y) {\tiny\n}; }}
% Now draw the black text.
\node[fill=none, text=black] at (\x,\y) {\tiny\n};
}
\newcommand{\sieve}[2]{
\def\cols{#1}
\def\rows{#2}
\begin{tikzpicture}[scale=.5]
\pgfmathtruncatemacro{\nmax}{\rows * \cols - 1}
% Draw light-colored polygon outlines for all numbers.
\begin{scope}[fill=white, draw=black!5!white, line width=4]
\foreach \n in {0,...,\nmax} {\polygon{\n}{\n}}
\end{scope}
% Draw thin-dark-lined and slightly filled polygons at intervals.
\begin{scope}[fill=black, fill opacity=.08,
draw=black, draw opacity=1,
line width=.5]
\foreach \n in {2,...,\nmax} {
\pgfmathparse{\n+1}\let\m\pgfmathresult
\foreach \i in {\m,...,\nmax} {
\pgfmathparse{Mod(\i,\n)==0? 1:0}
\ifnum\pgfmathresult=1
\polygon{\i}{\n}
\fi
}
}
\end{scope}
% Draw numeric labels.
\begin{scope}[fill=none, draw=black]
\foreach \n in {0,...,\nmax} {\numlabel{\n}}
\end{scope}
\end{tikzpicture}
}
\begin{document}
\sieve{12}{16}
\end{document}
Or, for grid starting at 1 instead of 0, you can tweak the calculation of \x and \y to be #1-1 instead of #1, and let \nmax be \rows * \cols instead of \rows * \cols - 1.
Here’s 10x10:
Color version of the polygon approach
I'm posting a second answer here because I think it's different enough from my previous answer. Changes I made:
- Added color. It is now much easier to identify individual numbers by eye.
- Removed non-prime polygons from walkthrough. This is truer to the classic approach. There's little sense in marking off multiples of 4, 6, 8, 9, 10, 12, 14, 15, 18, etc.
- Added prime factorization to coloring methodology. The more times a factor appears, the darker it appears in the coloring. For example, the powers primes such as 27 (3³), 25 (5²), and 49 (7²) have notably more intense color than their prime bases 3, 5, and 7. This is also true for powers of 2, which are shown using increasingly thick lines.
(Click image below for 2x larger version.)
Source code:
\documentclass{article}
\usepackage[margin=.25in]{geometry}
\pagestyle{empty}
\usepackage{tikz}
\usepackage{ifthen}
\newcommand{\setisprime}[1]{
% Sets \isprime based on #1.
\ifnum#1=1 \gdef\isprime{0} \else \gdef\isprime{1} \fi
\foreach \sip in {2, 3,5,...,#1} {
\pgfmathparse{\sip*\sip>#1? 1:0}
\ifthenelse{\pgfmathresult=1}{
% Early-out if \sip^2 > #1.
\breakforeach
}{
% Otherwise test if \sip divides #1.
\pgfmathparse{Mod(#1,\sip)==0? 1:0}
\ifthenelse{\pgfmathresult=1}{
\gdef\isprime{0}
\breakforeach
}{}
}
}
}
\newcommand{\setxy}[1]{
% Sets \x and \y to loction of cell #1.
\pgfmathtruncatemacro{\x}{Mod(#1-1,\cols)}
\pgfmathtruncatemacro{\y}{(#1-1) / \cols}
\pgfmathtruncatemacro{\y}{\cols - 1 - \y}
\pgfmathparse{2.5*(\x+.5)}\let\x\pgfmathresult
\pgfmathparse{2.5*(\y+.5)}\let\y\pgfmathresult
}
\newcommand{\numlabel}[2]{
% Draws label #2 at cell #1.
\setxy{\n}
\node[fill=none, text=black] at (\x,\y) {#2};
}
\newcommand{\drawpolygon}[2]{
% Draws polygon with #2 vertexes at cell #1.
\setxy{#1}
\ifthenelse{#2>1}{ % Polygon must have at least 2 sides.
\ifthenelse{#2<30}{ % Draw polygon if it has a small number of sides.
\filldraw (\x,\y) +(90:1)
\foreach \drawi in {1,...,#2} {-- +(\drawi/#2*360+90:1)} -- cycle;
}{ % Else approximate with circle.
\filldraw (\x,\y) circle(1);
}
}{}
}
\newcommand{\setpolygoncolor}[1]{
% Sets color based on #1.
\gdef\polycolor{black}
\ifnum#1=2\gdef\polycolor{black!50!white}\fi
\ifnum#1=3\gdef\polycolor{yellow!95!red}\fi
\ifnum#1=5\gdef\polycolor{yellow!0!red}\fi
\ifnum#1=7\gdef\polycolor{blue!75!green}\fi
\ifnum#1=11\gdef\polycolor{blue!70!red}\fi
\ifnum#1=13\gdef\polycolor{blue!40!red}\fi
\ifnum#1=17\gdef\polycolor{green!50!blue}\fi
\ifnum#1=19\gdef\polycolor{green!80!black}\fi
\ifnum#1=23\gdef\polycolor{green!50!red}\fi
\ifnum#1=29\gdef\polycolor{yellow!50!black}\fi
\ifnum#1=31\gdef\polycolor{orange!50!black}\fi
\ifnum#1=37\gdef\polycolor{red!50!black}\fi
\ifnum#1=41\gdef\polycolor{purple!50!black}\fi
\ifnum#1=43\gdef\polycolor{blue!50!black}\fi
\ifnum#1=47\gdef\polycolor{green!50!black}\fi
\ifnum#1=53\gdef\polycolor{white!50!black}\fi
\ifnum#1=59\gdef\polycolor{white!50!black}\fi
\ifnum#1=61\gdef\polycolor{white!50!black}\fi
\ifnum#1=67\gdef\polycolor{white!50!black}\fi
}
\newcommand{\sieve}[2]{
\def\cols{#1}
\def\rows{#2}
\begin{tikzpicture}[scale=.5]
\pgfmathtruncatemacro{\nmax}{\rows * \cols}
\foreach \n in {1,...,\nmax} {
\begin{scope}[fill=gray, fill opacity=.05,
draw=gray, draw opacity=.10,
line width=4]
\drawpolygon{\n}{\n}
\end{scope}
\setisprime{\n}
\ifthenelse{\isprime=1}{
\numlabel{\n}{\bf\n}
}{
\def\startintensity{.33}
\def\incrintensity{.10}
\def\intensity{\startintensity}
\def\m{\n}
\pgfmathtruncatemacro{\i}{\m / 2}
% Divide \m by \i until \m is extinguished.
% Increment \i each time it does not divide into \m.
\whiledo{\m>1}{
\setisprime{\i}
\pgfmathparse{Mod(\m,\i)==0? 1:0}
\ifthenelse{\pgfmathresult=1\and\isprime=1}{
\setpolygoncolor{\i}
\begin{scope}[fill=\polycolor, fill opacity=\intensity,
draw=\polycolor!85!black, draw opacity=\intensity,
line width=\intensity*1.5]
\drawpolygon{\n}{\i}
\end{scope}
\pgfmathtruncatemacro{\m}{\m / \i}
\pgfmathparse{\intensity + \incrintensity}\let\intensity\pgfmathresult
}{
\pgfmathtruncatemacro{\i}{\i - 1}
\def\intensity{\startintensity}
}
}
\begin{scope}[text=black, text opacity=.5]
\numlabel{\n}{\scriptsize\n}
\end{scope}
}
}
\end{tikzpicture}
}
\begin{document}
\sieve{10}{10}
\end{document}
Numbers up to 320:
