The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It iteratively marks the multiples of each prime as composite (i.e. not prime). It starts with the multiples of 2.
A good way to show the algorithm is using animations. Here the animate package is used together with TikZ. The darker the shade of red 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.
The PDF animation can be produced with the following settings:
% !TEX none
%\def\ShowStepByStep{}% Ignored in this case
\def\AnimateSieve{}%
%\def\AnimatedGif{}% Must be commented
For a 10×10, which requires a long compiling time, use
!TEX none
\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, for example with the following settings:
!TEX none
%\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:
!TEX none pdfcrop erathostenes-sieve.pdf convert -verbose -delay 100 -loop 0 -density 150 erathostenes-sieve-crop.pdf erathostenes-sieve.gif
Furthermore, there’s a paper version:
!TEX none
\def\ShowStepByStep{}%
%\def\AnimateSieve{}% This MUST be commented
%\def\AnimatedGif{}% This MUST be commented
\def\NumOfColumns{7}%
\def\NumOfRows{7}%
\def\FramesToHoldAtEnd{10}%
Non-square sizes can be produced as well by adjusting the value of NumOfColumns and NumOfRows.
This has been originally posted on Sieve of Eratosthenes in TikZ as answer to a question by the user azetina.
Edit and compile if you like:
%%% 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.
%%%
%%% Author: Peter Grill
%\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
% http://tex.stackexchange.com/questions/37709/
\newcommand{\IfNumberAlreadyMarked}[4][NonPrime]{% #1=prefix, #2=num
\pgfutil@ifundefined{pgf@sh@ns@#1#2}{#4}{#3}%
}
% http://tex.stackexchange.com/questions/20655/
\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.
}{%
\pgfmathtruncatemacro{\MaxMultiple}{\MaxNumber/\arabic{CountK}}%
\setcounter{CurrentMaxMultiplePlusOne}{\MaxMultiple}%
\stepcounter{CurrentMaxMultiplePlusOne}%
%
\setcounter{CountP}{2}%
\stepcounter{StepNumber}%
\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}
Click to download: eratosthenes-sieve.tex • eratosthenes-sieve.pdf
Open in Overleaf: eratosthenes-sieve.tex