![运行时未排版的宏](https://linux22.com/image/428889/%E8%BF%90%E8%A1%8C%E6%97%B6%E6%9C%AA%E6%8E%92%E7%89%88%E7%9A%84%E5%AE%8F.png)
我最近在看这个问题素数宏,我注意到 TeXbook 中显示的解决方案是在宏开发时排版素数。
然后我重新创建了一个与 TeXbook 解决方案非常相似的宏来查找前 [n] 个素数:
\documentclass{article}
\usepackage{amsmath}
\newif\ifprime
\newcount\numOfPrimes \newcount\i \newcount\n \newcount\res \newcount\limit
\def\testdivision{%
\res=\n \divide\res by\i \multiply\res by\i
\ifnum\res=\n \global\primefalse \global\advance\i by\limit\fi}
\def\isprime{{% <-- group
\i=3 \limit=\n \divide\limit by2 \global\primetrue
\loop\ifnum\i<\limit \testdivision \advance\i by2 \repeat}}
\def\printprime{%
\ifnum\numOfPrimes>1 , %
\else\ifnum\numOfPrimes=1 ~and~%the last prime to print
\fi\fi%
\number\n \advance\numOfPrimes by-1}
\def\printifprime{%
\isprime%test if n is prime
\ifprime \printprime\fi}
\def\primes#1{%
\ifnum#1=1 2\else\ifnum#1=2 2~and~3%
\else 2,~3\numOfPrimes=#1 \advance\numOfPrimes by-2 \n=5%
\loop\ifnum\numOfPrimes>0 \printifprime \advance\n by2 \repeat%
\fi\fi}
\begin{document}
The first 30 primes numbers are \primes{30}
\end{document}
当然,这个解决方案是有效的(并且肯定不是最快的),但我想知道如何改变\printprime
我编写的命令,以便它可以“存储”所有素数,然后一旦宏完成,它就会立即排版所有内容。
我看到其他解决方案这里用过的\noexpand
、、\expandafter
我不太理解它们,但我很确定这些命令用于存储素数而不对它们进行排版。
如果有人能帮助我,我将非常感激。
答案1
\documentclass{article}
\usepackage{amsmath}
\newif\ifprime
\newcount\numOfPrimes \newcount\i \newcount\n \newcount\res \newcount\limit
\def\testdivision{%
\res=\n \divide\res by\i \multiply\res by\i
\ifnum\res=\n \global\primefalse \global\advance\i by\limit\fi}
\def\isprime{{% <-- group
\i=3 \limit=\n \divide\limit by2 \global\primetrue
\loop\ifnum\i<\limit \testdivision \advance\i by2 \repeat}}
\def\storeprime#1{%
\ifnum\numOfPrimes>1 \addtolist#1{, }%
\else\ifnum\numOfPrimes=1 \addtolist#1{~and~}%the last prime to print
\fi\fi
\expandafter\addtolist\expandafter#1\expandafter{\number\n}\advance\numOfPrimes by-1}
\def\storeifprime#1{%
\isprime%test if n is prime
\ifprime \storeprime#1\fi}
\def\makelistofprimes#1#2{%
\def#1{}% initialize
\ifnum#2=1 \addtolist#1{2}\else\ifnum#2=2 \addtolist#1{2~and~3}%
\else \def#1{2,~3}\numOfPrimes=#2 \advance\numOfPrimes by-2 \n=5
\loop\ifnum\numOfPrimes>0 \storeifprime#1\advance\n by2 \repeat
\fi\fi}
\def\addtolist#1#2{%
\expandafter\def\expandafter#1\expandafter{#1#2}%
}
\begin{document}
\makelistofprimes\mylist{30}
\show\mylist % show the result on the terminal
The first 30 primes numbers are \mylist
\end{document}
代码中的某些宏已被修改,以接受要填充的列表的名称作为参数。关键是\addtolist
,使用合适的链\expandafter
将导致列表扩展为其先前的值。\number
添加找到的素数时需要类似的链来进行扩展。
我们可以这样想\def\addtolist#1#2{\edef#1{#1#2}}
,但是这会破坏的使用~
。
终端上输出:
> \mylist=macro:
->2,~3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109~and~113.
基于埃拉托斯特尼筛选法的更高效算法的实现:
\documentclass{article}
% Rosser, p_n < n(log n + 2 log log n) for n ≥ 2
% J. B. Rosser, The n-th prime is greater than n log n,
% Proc. London Math. Soc., ser. 2, 45 (1939), 21–44
% Sieve of Eratosthenes algorithm taken from
% https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode
\ExplSyntaxOn
\NewDocumentCommand{\makelistofprimes}{smm}
{% #1 = name of the list, #2 = number of primes to generate
\seq_clear_new:c { l_eratosthenes_#2_seq }
\int_compare:nTF { #3 = 1 }
{ \seq_put_right:cn { l_eratosthenes_#2_seq } { 2 } }
{ \__eratosthenes_list:nn { #2 } { #3 } }
\IfBooleanT {#1} { \seq_use:cn { l_eratosthenes_#2_seq } {,~} }
}
\int_new:N \l__eratosthenes_count_int
\int_new:N \l__eratosthenes_step_int
\cs_new_protected:Nn \__eratosthenes_list:nn
{
\intarray_new:cn { g__eratosthenes_#1_intarray }
{ \fp_eval:n { ceil(#2*(ln(#2)+2*ln(ln(#2)))) } }
\int_set:Nn \l__eratosthenes_count_int { \intarray_count:c { g__eratosthenes_#1_intarray } }
\intarray_gset:cnn { g__eratosthenes_#1_intarray } { 1 } { 1 } % 1 is not prime
\int_step_inline:nnn { 2 } { \fp_eval:n { floor( sqrt(\l__eratosthenes_count_int) ) } }
{
\int_compare:nT { \intarray_item:cn { g__eratosthenes_#1_intarray } { ##1 } = 0 }
{% the current number is prime
\int_step_inline:nnnn { ##1*##1 } { ##1 } { \l__eratosthenes_count_int }
{ \intarray_gset:cnn { g__eratosthenes_#1_intarray } { ####1 } { 1 } }
}
}
\int_zero:N \l__eratosthenes_step_int
\int_while_do:nn { \seq_count:c { l_eratosthenes_#1_seq } < #2 }
{
\int_incr:N \l__eratosthenes_step_int
\int_compare:nT { \intarray_item:cn { g__eratosthenes_#1_intarray } { \l__eratosthenes_step_int } = 0 }
{
\seq_put_right:cx { l_eratosthenes_#1_seq } { \int_eval:n { \l__eratosthenes_step_int } }
}
}
}
\ExplSyntaxOff
\begin{document}
The first 100 prime numbers are \makelistofprimes*{x}{100}
The first 10 prime numbers are \makelistofprimes*{y}{10}
\end{document}
这会将列表保存为一个序列,然后可以通过多种方式重复使用。出于实施原因,每次调用都需要一个新名称(这可能会更改)。
这个想法是分配一个整数数组,但这需要指定其中的项目数,因此我使用了一个界限n在引用的文章中找到第 1 个素数。数组最初填充了零,因此使用 1 作为非素数的标记更为简单。
接下来,筛法的实现与参考的维基百科页面相同,唯一的区别是 1 和 0 互换了。最后,通过遍历数组填充序列,拾取素数,直到我们达到n其中。
答案2
这里有一个可扩展但缓慢且低效的方法,基于递归宏来执行试除法,逐个按升序测试奇数自然数集合的每个元素,将要测试的奇数自然数除以已经找到的素数的平方不大于要测试的奇数自然数的平方。
除以这些数字就足够了,因为
- 将一个自然数分成两个自然因数时,要么两个因数都等于该数的平方根(这种情况仅发生在平方数中),要么一个因数小于该数的平方根,而另一个因数大于该数的平方根。
- 在任何情况下,已找到的素数集合都至少包含一个大于要测试的数字的平方根的元素。这可以从伯特兰-切比雪夫定理轻松推导出来:
“对于每个 n>1,总有至少一个素数 p 使得 n<p<2n。”
反之亦然:
对于每个偶数 n>2,总有至少一个素数 p 使得 n/2 < p < n。
对于每个奇数 n>3,总有至少一个素数 p 使得 (n-1)/2 < p < (n-1)。
查看 sqrt(n) <= n/2 和 sqrt(n) <= (n-1)/2 的情况。
\numexpr
来自 ε-TeX 扩展的用于进行算术运算。这和上面提到的条件“其平方不大于要测试的奇数自然数”限制了数字的范围。您可以使用包的可扩展例程 bigintcalc但这不会使事情变得更快。
由于您要求一次性提供整个素数列表,因此在递归过程中,迄今为止找到的素数会在宏参数中累积。因此,另一个值得注意的限制是可以存储为宏参数的标记数量。
该套路首次\primes{⟨natural number k⟩}
⟨k⟩素数作为无分隔/花括号嵌套参数的列表。
该套路首次\PrintPrimes{⟨natural number k⟩}
⟨k⟩素数作为逗号和空格分隔的列表。 (\PrintPrimes
对通过创建的列表的元素进行迭代\primes
,去掉花括号并在每个元素前添加一个逗号和一个空格,但列表的第一个元素除外。\relax
用作标记列表末尾的“标记标记”。)
由于\romannumeral
-expansion,两个例程在触发两个扩展步骤后/在\primes
“\PrintPrimes
命中”\expandafter
两次后才提供结果。
假设两种方案⟨k⟩是 TeX 可以处理的非正整数范围内的非正整数,因此不会默默传递任何标记。
\documentclass{article}
\newcommand\UDExchange[2]{#2#1}%
\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%
\newcommand\UDfirstofone[1]{#1}%
\csname @ifdefinable\endcsname\UDstopromannumeral{\chardef\UDstopromannumeral=`\^^00}%
\newcommand\primes[1]{%
\romannumeral
\ifnum#1<1 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral}{%
\ifnum#1=1 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral{2}}{%
\expandafter\expandafter\expandafter\UDfirstofone
\expandafter\primesloop\expandafter{\expandafter5\expandafter}%
\expandafter{\number\numexpr#1-2\relax}{3}\relax{{3}}%
}%
}%
}%
\csname @ifdefinable\endcsname\primesloop{%
% #1 - number to test
% #2 - amount of primes still to find
% #3 - current element of remaining list of primes found so far
% #4 - remaining elements of remaining list of primes found so far
% #5 - list of primes already found
\long\def\primesloop#1#2#3#4\relax#5{%
{\ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral{2}#5}}{%
\ifnum\number\numexpr#3*#3\relax>#1 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi%
{% Hooray, a prime!
\expandafter\expandafter\expandafter\UDfirstofone
\expandafter\primesloop\expandafter{\number\numexpr#1+2\expandafter\relax\expandafter}%
\expandafter{\number\numexpr#2-1\relax}#5{#1}\relax{#5{#1}}%
}{%
\ifnum\number\numexpr(#1/#3)*#3\relax=#1 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{% Hooray, a composite!
\expandafter\expandafter\expandafter\UDsecondoftwo
\expandafter\primesloop\expandafter{\number\numexpr#1+2\relax}{#2}#5%
}%
{% Trial-division by the next prime already found.
\expandafter\UDsecondoftwo\primesloop{#1}{#2}#4%
}%
\relax{#5}%
}%
}%
}%
}%
\newcommand\PrintPrimes[1]{%
\romannumeral
\expandafter\expandafter\expandafter\UDExchange
\expandafter\expandafter\expandafter{\primes{#1}}{\PrintPrimesLoop{}{}}\relax
}
\newcommand\PrintPrimesLoop[3]{%
\ifx\relax#3\expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral#2}{\PrintPrimesLoop{, }{#2#1#3}}%
}%
\begin{document}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{1}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{2}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{3}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{4}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{10}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\primes{100}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{1}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{2}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{3}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{4}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{10}}%
\message{^^J\meaning\test^^J}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{\PrintPrimes{100}}%
\message{^^J\meaning\test^^J}
\end{document}
当将上述示例保存为test.tex
并编译它时,控制台/调用 latex 的 shell 窗口显示以下内容:
$ pdflatex test.tex
This is pdfTeX, Version 3.14159265-2.6-1.40.21 (TeX Live 2020) (preloaded format=pdflatex)
restricted \write18 enabled.
entering extended mode
(./test.tex
LaTeX2e <2020-10-01> patch level 4
L3 programming layer <2021-01-09> xparse <2020-03-03>
(/usr/local/texlive/2020/texmf-dist/tex/latex/base/article.cls
Document Class: article 2020/04/10 v1.4m Standard LaTeX document class
(/usr/local/texlive/2020/texmf-dist/tex/latex/base/size10.clo))
(/usr/local/texlive/2020/texmf-dist/tex/latex/l3backend/l3backend-pdftex.def)
(./test.aux)
macro:->{2}
macro:->{2}{3}
macro:->{2}{3}{5}
macro:->{2}{3}{5}{7}
macro:->{2}{3}{5}{7}{11}{13}{17}{19}{23}{29}
macro:->{2}{3}{5}{7}{11}{13}{17}{19}{23}{29}{31}{37}{41}{43}{47}{53}{59}{61}{67
}{71}{73}{79}{83}{89}{97}{101}{103}{107}{109}{113}{127}{131}{137}{139}{149}{151
}{157}{163}{167}{173}{179}{181}{191}{193}{197}{199}{211}{223}{227}{229}{233}{23
9}{241}{251}{257}{263}{269}{271}{277}{281}{283}{293}{307}{311}{313}{317}{331}{3
37}{347}{349}{353}{359}{367}{373}{379}{383}{389}{397}{401}{409}{419}{421}{431}{
433}{439}{443}{449}{457}{461}{463}{467}{479}{487}{491}{499}{503}{509}{521}{523}
{541}
macro:->2
macro:->2, 3
macro:->2, 3, 5
macro:->2, 3, 5, 7
macro:->2, 3, 5, 7, 11, 13, 17, 19, 23, 29
macro:->2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239
, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 33
7, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 4
33, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
541
(./test.aux) )
No pages of output.
Transcript written on test.log.