· 7 years ago · Sep 16, 2018, 02:14 PM
1documentclass[t]{beamer}
2usepackage[utf8]{inputenc}
3usepackage[T1]{fontenc}
4usepackage{lmodern}
5usetheme{default}
6
7usepackage{geometry}
8
9usepackage{microtype}% Allow comma into margin in list of primes
10usepackage{xstring}% String comparison
11usepackage{tikz}% Drawing
12usetikzlibrary{calc}% Coordinate calculations
13usetikzlibrary{backgrounds}% Apply shading on background layer
14usepackage{animate}
15
16
17begin{document}
18
19
20
21defNumOfColumns{10}% See note above if product of
22defNumOfRows{10}% NumOfColumns and NumOfRows > 100.
23
24%% FramesToHoldAtEnd should be larger than the number of primes
25%% so that they can get highlighted at the end of the process
26defFrameRate{1}%
27defFramesToHoldAtStart{1}%
28defFramesToHoldAtEnd{25}% 25 is enough for 10x10
29
30
31defScale{0.6}% May need tweaking..
32
33
34defPrimeColor{green!80!red}% Shade for primes found previously
35defNewPrimeColor{green!80!red}% Shade for prime just found
36defNewPrimeText{red}% Color for primes in list
37defNonPrimeColor{yellow!80!red}% Shade for non-primes
38
39
40%% List of Primes is typeset into a node of this width.
41defTextWidth{2.0cm}%
42
43
44% Simplifies code below if we just redefine these two from the
45% animate package so that they do don't much.
46%renewenvironment{animateinline}[1]{begingroup}{endgroup}%
47%renewcommand{newframe}[1][]{newpage}%
48
49
50
51
52%%% ---------------------------------------------------------------
53%%% Should not need to adjust anything below this line
54%%%
55pgfmathtruncatemacro{MaxNumber}{NumOfRows*NumOfColumns}%
56pgfmathtruncatemacro{MaxValue}{sqrt(MaxNumber)}%
57
58% Choose opacity so that we can have the max number of shades
59%pgfmathsetmacro{Opacity}{1.0/min(5,MaxValue-1)}%
60pgfmathsetmacro{Opacity}{0.4}%
61
62%% The Sieve algorithm requires that once a number is marked
63%% as non-prime (i.e., was a multiple of some other number)
64%% we don't need to check multiples of that number as they
65%% have already been marked as non-prime.
66%%
67%% Usually one would use an array and set a flag. But since
68%% variables with numbers are difficult with TeX, we can
69%% define a node named with the number that is non-prime.
70%% Then just check that the node exists to see if it was
71%% marked as non-prime.
72
73makeatletter
74% Mark number as either "Prime" or "NonPrime".
75newcommand*{MarkNumber}[2][NonPrime]{node (#1#2) {}}% #1=prefix, #2=num
76
77% https://tex.stackexchange.com/questions/37709/how-can-i-know-if-a-node-is-already-defined
78newcommand{IfNumberAlreadyMarked}[4][NonPrime]{% #1=prefix, #2=num
79pgfutil@ifundefined{pgf@sh@ns@#1#2}{#4}{#3}%
80}
81
82% https://tex.stackexchange.com/questions/20655/how-to-undo-a-def-i-e-need-a-undef-capability
83newcommand*@nameundef[1]{%
84globalexpandafterletcsname #1endcsname@undefined%
85}
86
87%% Since we repeat the process from the beginning for the animated
88%% version, use this to clear the nodes so that the numbers are
89%% not marked as multiples of a number from the previous run.
90newcommand{ClearAllNumberedNodeNames}{%
91foreach i in {1,...,MaxValue}{%
92 @nameundef{pgf@sh@ns@NonPrimei}%
93 @nameundef{pgf@sh@ns@Primei}%
94}%
95}
96makeatother
97
98%% The Sieve algorithm skips multiples of numbers already marked as
99%% non-prime. So, to number the individual steps, need to use
100%% a counter.
101%% i.e., Step 4 is processing multiples of 5 (since we skip 4).
102newcounter{StepNumber}%
103
104
105%%% ---------------------------------------------------------------
106%%%
107%%% Titles and Labels
108%%%
109
110newcommandListOfPrimes{}
111newcommandAddToListOfPrimes[2][fill=PrimeColor]{%
112IfStrEq{ListOfPrimes}{}{%
113 defSeparator{}% First member of list of primes
114}{%
115 defSeparator{, }% Subsequent member of list of primes
116}%
117%
118FillCellForGivenNumber[#1]{#2};%
119globaledefListOfPrimes{ListOfPrimesSeparator#2}%
120MarkNumber[Prime]{#2};%
121}
122
123newcommand*{ClearListOfPrimes}{%
124ClearAllNumberedNodeNames;%
125renewcommand{ListOfPrimes}{}%
126}
127
128
129
130
131% å³ä¾§æ˜¾ç¤ºç´ 数列表，暂时ä¸ç”¨
132newcommand*{Phantom}[1]{}%
133newcommand*{ShowListOfPrimesNode}{%
134IfStrEq{ListOfPrimes}{}{%
135 %% Empty list of primes, so don't want to show anything.
136 %% Just add phantom spacing
137 renewcommand*{Phantom}[1]{phantom{##1}}%
138}{%
139 renewcommand*{Phantom}[1]{##1}%
140}%
141
142%node [below right, xshift=0.5em, yshift=-0.5ex, align=left, text width=TextWidth]
143% at (NumOfColumns,-1)
144% {Phantom{textbf{Primes:}}};
145
146%node [below right, xshift=0.2em, yshift=-3.5ex, align=left, text width=TextWidth]
147% at (NumOfColumns,-1)
148% {Phantom{textbf{textcolor{NewPrimeText}{raggedleftListOfPrimes}}}};
149}
150
151%%% ---------------------------------------------------------------
152
153%%%
154%%% Step 1: Create a list of integers 2...n
155%%%
156newcommand*{DrawGridWithNumbers}{%
157begin{scope}% Add numbers to each node
158 draw (0,-1) -- ($(0,-NumOfRows-1)$);
159 foreach col in {1,...,NumOfColumns} {%
160 draw (col,-1) -- ($(col,-NumOfRows-1)$);
161
162 draw (0,-1) -- (NumOfColumns,-1);
163 foreach row in {1,...,NumOfRows}{%
164 pgfmathtruncatemacro{value}{col+NumOfColumns*(row-1)}
165 IfEq{value}{1}{
166 %% Suppress number 1 from being printed since first
167 %% step of Sieve of Eratosthenes algorithm is to
168 %% create a list of integers 2...n
169 }{
170 node at ($(col,-row)-(0.5,0.5)$) {value};
171 }
172 draw (0,-row-1) -- (NumOfColumns,-row-1);
173 }
174 }
175end{scope}
176
177%% Since we just drew the grid we should ensure that none
178%% of the numbered nodes exist (i.e., that no numbers
179%% are marked as non-prime. And reset list of primes.
180
181ClearListOfPrimes;
182ClearAllNumberedNodeNames;
183
184%ShowListOfPrimesNode;
185}
186
187newcommand*{FillCellForGivenNumber}[2][]{%
188%% #1 = fill options
189%% #2 = number
190%%
191pgfmathtruncatemacro{Column}{mod(#2,NumOfColumns)}%
192IfEq{Column}{0}{pgfmathtruncatemacro{Column}{NumOfColumns}}{}%
193pgfmathtruncatemacro{Row}{(#2-1)/NumOfColumns+1}%
194
195begin{scope}[on background layer]
196 fill [#1]
197 (Column-1,-Row) --
198 ($(Column-1,-Row)+(1,0)$) --
199 ($(Column-1,-Row)+(1,-1)$) --
200 (Column-1,-Row-1) --
201 cycle;
202end{scope}
203}
204
205
206
207newcommand*{ColorMultiplesOf}[2][0]{%
208%% If only 1 arg is given (i.e., #1=0), then
209%% #2 = the multiple for which the coloring is applied
210%%
211%% If two args are given (i.e., #1 != 0) then
212%% #1 = Value of MaxMultiple (used for animated version)
213%% In the two arg case we run the entire sequence
214%% from the beginning up until the multiple #1*#2
215%% is reached.
216
217IfEq{#1}{0}{% Run the entire sequence
218 pgfmathtruncatemacro{MaxMultiple}{MaxNumber/#2}
219}{% Run sequence up until number given for animating
220 defMaxMultiple{#1}
221}
222
223foreach i in {2,...,MaxMultiple} {
224 pgfmathtruncatemacro{NonPrimeNumber}{i*#2}
225 FillCellForGivenNumber[
226 fill=NonPrimeColor,
227 fill opacity=Opacity
228 ]
229 {NonPrimeNumber};
230 MarkNumber[NonPrime]{NonPrimeNumber};
231}
232}
233
234
235newcommand*{BuildFrameInternals}[2][0]{%
236%% #1 = current multiple to which to build the pattern up to
237%% if #1=0 and #2=MaxValue, then we are in an end hold frame
238%% #2 = number of whose multiples we are eliminating in this step
239%% if #2=1, then only draw grid (provides hold frame at start)
240
241%AddTitleNode;% Print Main title if AnimateSieve is defined
242
243DrawGridWithNumbers;
244IfEq{#2}{1}{%
245 %% This is a hold frame at start so only show grid of numbers
246 %AddInitialSubTitleNode{#2};
247}{%
248 IfEq{#2}{2}{%
249 %% No pre-processing steps to be done in this case
250 }{%
251 %% Since we are eliminating multiples of a number
252 %% other than 2, we need to get the table up to
253 %% the state where all the multiples of 2...(#2-1)
254 %% are eliminated.
255
256 pgfmathsetmacro{PreviousMultiple}{#2 - 1}%
257 foreach n in {2,...,PreviousMultiple} {%
258 IfNumberAlreadyMarked[NonPrime]{n}{%
259 %% Skip. Multiples are already marked as non-prime
260 %% since this number is a multiple of a smaller
261 %% prime.
262 }{%
263 %% This is a prime. Mark it as prime, and mark
264 %% its multiples as non-prime.
265 AddToListOfPrimes[fill=PrimeColor]{n};
266 ColorMultiplesOf{n};
267 }
268 }
269 }
270
271 IfNumberAlreadyMarked[NonPrime]{#2}{%
272 %% Already taken care of in a previous run. This test
273 %% is needed to cover the case where the value of the
274 %% sqrt{NumberOfColumns x NumberOfRows) is not prime.
275 %% For example: 10x10.
276 }{%
277 %% Now eliminate the numbers up to the current state
278 AddToListOfPrimes[fill=NewPrimeColor]{#2};
279 ColorMultiplesOf[#1]{#2};
280 }
281
282 %% If we are holding the very final result don't print title.
283 %% This is the case when #2=MaxValue and #1=0.
284 %%
285 %% Need to do this at the end so that we can access
286 %% which numbers have been marked as non-prime.
287
288 IfEq{#2}{MaxValue}{%
289 %IfEq{#1}{0}{%
290 %% This is the final hold frame
291 %SubTitleFinal;
292
293 IfNumberAlreadyMarked[NonPrime]{#2}{%
294 }{%
295 IfNumberAlreadyMarked[Prime]{#2}{%
296 %% In this case, #2 is not a new prime so
297 %% correct its color. So, don't add it to the
298 %% list of primes, but correct ensure its
299 %% color corresponds to an old prime
300 FillCellForGivenNumber[fill=PrimeColor]{#2};
301 }{%
302 %% In this case, #2 is a new prime so
303 %% add it to the list of primes,
304 AddToListOfPrimes[fill=NewPrimeColor]{#2};
305 }%
306 }%
307
308 %% But since this is the final hold frame, we need
309 %% to mark all the numbers not already marked as
310 %% non-prime as prime. Do one at at time, so that
311 %% this can be seen in the animation.
312
313 pgfmathtruncatemacro{StartValue}{MaxValue+1}%
314 foreach p in {StartValue,...,MaxNumber}{%
315 IfNumberAlreadyMarked[NonPrime]{p}{%
316 %% This number has been marked as non-prime
317 }{%
318 %% This is a prime
319 IfNumberAlreadyMarked[Prime]{p}{%
320 %% Already found this prime earlier.
321 %% So ensure it has appropriate fill.
322 AddToListOfPrimes[fill=PrimeColor]{p};%
323 }{%
324 %% New prime: Mark it as such, and
325 %% break out to complete this frame.
326 AddToListOfPrimes[fill=NewPrimeColor]{p};%
327 MarkNumber[Prime]{p};%
328 %AddSubTitleNode{};%
329 breakforeach;%
330 }%
331 }%
332 }%
333 %}{%
334 %% Not final hold frame, so normal title
335 %AddSubTitleNode{#2};%
336 %}%
337 }{%
338 %AddSubTitleNode{#2};%
339 }%
340}%
341%ShowListOfPrimesNode%
342}%
343
344
345
346newcommand*{BuildFrame}[2][0]{%
347%% #1 = current multiple to which to build the pattern up to
348%% #2 = number of whose multiples we are eliminating in this step
349%% if #2=1, then only draw grid (provides hold frame at start)
350noindent%
351centering%
352begin{tikzpicture}[yscale=Scale]%
353 BuildFrameInternals[#1]{#2};
354end{tikzpicture}%
355%
356}%
357
358newcommand*{BuildFinalFrame}{%
359noindent%
360centering%
361begin{tikzpicture}[yscale=Scale]%
362 %AddTitleNode;% Print Main title if AnimateSieve is defined
363 %AddSubTitleNode{};
364 DrawGridWithNumbers;
365 foreach p in {2,...,MaxValue}{%
366 IfNumberAlreadyMarked[NonPrime]{p}{%
367 }{%
368 AddToListOfPrimes[fill=PrimeColor]{p};
369 ColorMultiplesOf{p};
370 }%
371 }%
372 pgfmathtruncatemacro{StartValue}{MaxValue+1}%
373 foreach p in {StartValue,...,MaxNumber}{%
374 IfNumberAlreadyMarked[NonPrime]{p}{%
375 %% This number has already been marked as non-prime
376 }{%
377 %% This is a prime. Since we are just printing out
378 %% the final results we don't distinguish between a
379 %% newly found prime and a prime found previously.
380 AddToListOfPrimes[fill=PrimeColor]{p};
381 }%
382 }%
383
384 %ShowListOfPrimesNode;
385end{tikzpicture}%
386%
387}
388
389newcounter{CountK}
390newcounter{CountP}
391newcounter{CurrentMaxMultiplePlusOne}
392%
393
394
395
396begin{frame}{Sieve of Eratosthenes}
397begin{animateinline}[autopause,controls, buttonsize=1.2em, buttonbg=1:0.78:0,buttonfg=0.2:0.2:0.2]{FrameRate}%
398 stepcounter{StepNumber}%
399 setcounter{CountK}{0}%
400 whiledo{arabic{CountK} < FramesToHoldAtStart}{%
401 BuildFrame[0]{1}% initial hold frame
402 newframe[FrameRate]%
403 stepcounter{CountK}%
404 }%
405 %
406 setcounter{CountK}{2}%
407 whiledo{numexprarabic{CountK}-1 < MaxValue}{%
408 IfNumberAlreadyMarked[NonPrime]{arabic{CountK}}{%
409 %% value{CountK} has already been marked as non-prime.
410 %% Hence, so so are its multiples, and we can skip it.
411 }{%
412%% Question 1: Should be able to replace three lines following with
413%% this. But then animation seems to skip the loop below
414% pgfmathsetcounter{CurrentMaxMultiplePlusOne}{1+(MaxNumber/arabic{CountK})}%
415 pgfmathtruncatemacro{MaxMultiple}{MaxNumber/arabic{CountK}}%
416 setcounter{CurrentMaxMultiplePlusOne}{MaxMultiple}%
417 stepcounter{CurrentMaxMultiplePlusOne}%
418 %
419 setcounter{CountP}{2}%
420 stepcounter{StepNumber}%
421%% Question 2: Ideally would prefer to use the following syntax
422%% but this does not even compile!!! But, an indentical
423%% syntax works in the above `whiledo`, where the value of
424%% MaxValue was also defined by pgfmathtruncatemacro
425% whiledo{numexprarabic{CountP}-1 < MaxMultiple}{%
426 whiledo{arabic{CountP} < arabic{CurrentMaxMultiplePlusOne}}{%
427 BuildFrame[theCountP]{theCountK}%
428 newframe[FrameRate]%
429 stepcounter{CountP}%
430 }%
431 }%
432 stepcounter{CountK}%
433 }%
434 % At end, add hold frames in case we are looping
435 %
436 % There needs to be enough of these so that each of the
437 % primes (those not colored in) get highlighted at each frame.
438 %
439 setcounter{CountK}{2}%
440 whiledo{numexprarabic{CountK}-1 < FramesToHoldAtEnd}{%
441 BuildFrame{MaxValue}%
442 newframe[FrameRate]%
443 stepcounter{CountK}%
444 }
445end{animateinline}%
446end{frame}
447end{document}