如何用 LaTeX 自动绘制素数分解树状图?

如何用 LaTeX 自动绘制素数分解树状图?

我想要一个简单的界面自动地绘制素数分解的树形图。例如,通过调用以下代码,

\PrimeTree{36}
\PrimeTree{90}
\PrimeTree{112}
\PrimeTree{612}
\PrimeTree{7875}
\PrimeTree{22230}

我们将得到以下输出。

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

如何在 LaTeX(PSTricks、TikZ、Asymptote、Metapost 等)中做到这一点?

我的未经教育的努力如下。

\documentclass[border=3pt,preview,varwidth,multi]{standalone}
\usepackage{pst-tree}
\psset{levelsep=1,treesep=1,nodesep=2pt}


\begin{document}

\preview
\psTree{\TR{36}}
    \Tcircle{2}
    \psTree{\TR{18}}
        \Tcircle{2}
        \psTree{\TR{9}}
            \Tcircle{3}
            \Tcircle{3}
        \endpsTree
    \endpsTree
\endpsTree
\endpreview

\preview
\psTree{\TR{90}}
    \Tcircle{2}
    \psTree{\TR{45}}
        \Tcircle{3}
        \psTree{\TR{15}}
            \Tcircle{3}
            \Tcircle{5}
        \endpsTree
    \endpsTree
\endpsTree
\endpreview

\preview
\psTree{\TR{112}}
    \Tcircle{2}
    \psTree{\TR{56}}
        \Tcircle{2}
        \psTree{\TR{28}}
            \Tcircle{2}
            \psTree{\TR{14}}
                \Tcircle{2}
                \Tcircle{7}
            \endpsTree
        \endpsTree
    \endpsTree
\endpsTree
\endpreview

\preview
\psTree{\TR{612}}
    \Tcircle{2}
    \psTree{\TR{306}}
        \Tcircle{2}
        \psTree{\TR{153}}
            \Tcircle{3}
            \psTree{\TR{51}}
                \Tcircle{3}
                \Tcircle{17}
            \endpsTree
        \endpsTree
    \endpsTree
\endpsTree
\endpreview

\preview
\psTree{\TR{7875}}
    \Tcircle{3}
    \psTree{\TR{2625}}
        \Tcircle{3}
        \psTree{\TR{875}}
            \Tcircle{5}
            \psTree{\TR{175}}
                \Tcircle{5}
                \psTree{\TR{35}}
                    \Tcircle{5}
                    \Tcircle{7}
                \endpsTree
            \endpsTree
        \endpsTree
    \endpsTree
\endpsTree
\endpreview

\preview
\psTree{\TR{22230}}
    \Tcircle{2}
    \psTree{\TR{11115}}
        \Tcircle{3}
        \psTree{\TR{3705}}
            \Tcircle{3}
            \psTree{\TR{1235}}
                \Tcircle{5}
                \psTree{\TR{247}}
                    \Tcircle{13}
                    \Tcircle{19}
                \endpsTree
            \endpsTree
        \endpsTree
    \endpsTree
\endpsTree
\endpreview
\end{document}

为了感谢您的努力,我只能提供以下内容!

enter image description here

答案1

编辑(2017/09/01 & 02):

版本 1.2o 弃用了此处使用的一些宏,因此答案已更新。这次,我用提供的等替换了的用法\if...\else...\fixint这样\xintiiifOne可以安全地选择分支,并避免在用户级别firstoftwo/secondoftwo出现类似情况。\expandafter\expandafter\expandafter


注意:xint 手册还包含实现可扩展 Rabin-Miller 强伪素数测试的代码……


这个答案是分阶段演变的。新的贡献被添加到底部(除了我放在顶部的图像)。

  1. \factorize以编程方式生成输入的因式分解N。输出放在宏中\factors。例如N=36,对于,\factors展开为{{}{}{36}}{{2}{2}{9}}{{3}{2}{1}}。每个连续三元组是{p}{k}{m}其中是的因子p^k,以及除以它和所有前面的因子的结果。第一个三元组有点麻烦,这解释了一些显示代码。最初显示使用表格。pNmN{}{}{N}\expandafter\@gobble\factors

  2. 然后我添加了代码,使用pst-tree来根据 中可用的结果生成树 \factors。我还添加了代码,用于内联打印分解过程。

  3. 我现在使用 来添加代码TikZ+forest,自从看到 Qrrbrbirlbel 的回答中很好地使用了 后,我学到了一些。forest树的代码还合并了inline因式分解的版本。

我仅使用pst-treeforest来显示,而不是计算因式分解。树的pst-tree和语法都允许使用简单的方法从到树:两个标记列表逐步填充;如果使用带有的本机语法,由于括号和,这将更加困难。forest\factorsTikZchild{}


使用以下方式生成的树木图像forest

forest-7

forest-9

forest-11

forest-13


使用树木图像pst-tree(由普斯特。)这里有一些示例(代码也有变体,1当它们是指数时不显示它们)。对于制作树的一些其他方法,例如使用 TikZ 的子节点和节点,命令\factors准备的宏\factorize可能应该以略有不同的方式完成。

22230

2147483644

128154740640622513993964746937443811328

1689242184972


我也建议使用包来回答一半的问题信特用于算术计算(对任意大数)。该命令\factorize{N}生成\factors一个包含三元组列表的宏{p}{k}{m},其中p是分解因式时出现的素数,k是其指数,是除以m的结果,以及所有先前对应于较小素数的因数。因此,最后一个三元组有,第一个是。Np^km=1{}{}{N}

然后可以从这个宏构造树\factors;这里我只需要\displayfactorization使用表格显示结果(我使用了一些宏信特转换\factors为表格中的内容)。有一个可选参数用于设置第二列的宽度。

我用数字打印包用于打印非常长的数字而不超出页面的物理限制。

该算法非常蹩脚:首先测试除以 2,然后是 3,然后是 5,以及所有连续的奇数整数,直到N减为 1。

\factors除了被填满之外,对 TeX 内存没有影响。

\count如果仅使用 TeX寄存器(以及为了方便起见的 eTeX )来完成,算法当然会更快\numexpr,但这会将其限制为数字< 2^{31}

更新:我已经加入了通常的停机测试以不超过 n 的平方根,当因式分解以“大”素数结束时,使得事情变得更有效率(添加了两个这样的例子)。

\documentclass{article}
\usepackage{xint}
\usepackage{xintexpr}
\usepackage[T1]{fontenc}
\usepackage{array}
\usepackage[np]{numprint}
\AtBeginDocument{\npthousandsep{,\hskip .1pt plus .02pt minus .02pt}}

\catcode`\_ 11

\def\factorize#1{%
    \edef\factorize_N{#1}%
    \def\factorize_exp{0}%
    \edef\factors{{{}{}{\factorize_N}}}%
    \factorize_i
}

\def\factorize_i{%
    \xintiiifOdd{\factorize_N}%
      {\factorize_ii}%
      {\edef\factorize_exp{\xintInc{\factorize_exp}}%
       \edef\factorize_N  {\xintHalf{\factorize_N}}%
       \factorize_i}%
}

\def\factorize_ii{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{2}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {\def\factorize_M{3}%
       \def\factorize_exp{0}%
       \factorize_iii}%
}

\def\factorize_iii{%
    \xintAssign\xintiiDivision\factorize_N\factorize_M\to\factorize_Q\factorize_R
    \xintiiifSgn{\factorize_R}%
      {% never happens: remainder can not be negative
      }%
      {% case of vanishing remainder
       \edef\factorize_exp{\xintInc{\factorize_exp}}%
       \let\factorize_N\factorize_Q 
       \factorize_iii
      }%
      {\factorize_iv}% 
}

\def\factorize_iv{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{\factorize_M}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {% here N>1, N=QM+R (0<R<Q) is < M(Q+1) and N has no prime factors
       % at most equal to M. If a prime P>M divides N, the
       % quotient N/P will be < Q+1, hence at most Q. If Q<=M, then
       % N/P must be 1 else there would be some prime <=M dividing N.
       % no \xintiiifGeq ...
       % \xintiifCmp will have branches for each of <, =, >, less convenient
       % So we use \xintiiifLt which exists, and permute the branches
       % compared to original code
       \xintiiifLt\factorize_M\factorize_Q
         {% we go on testing with bigger factors
          % or \edef\factorize_M{\xintInc{\xintInc{\factorize_M}}} perhaps
          \edef\factorize_M{\xintiiAdd \factorize_M 2}%
          \def\factorize_exp{0}%
          \factorize_iii
         }%
         {% implies that N is prime
          \edef\factors{\factors{{\factorize_N}{1}{1}}}% we stop here
         }%
      }%
}

\catcode`\_ 8

\def\auxiliarymacroa #1{\auxiliarymacrob #1}
\def\auxiliarymacrob #1#2#3{${#1}^{#2}$&\np{#3}\tabularnewline\hline}

\newcommand*\displayfactorization[1][.2\linewidth]{%
   \begin{tabular}{>{\rule{0pt}{11pt}}c|>{\raggedright}p{#1}}%
   \xintApplyUnbraced\auxiliarymacroa{\factors}
   \end{tabular}\hskip.5em plus .125em minus .125em }

%for testing:
% \def\displayfactorization{\meaning\factors}

\pagestyle{empty}
\begin{document}\thispagestyle{empty}\ttfamily

\noindent\factorize{36}\displayfactorization
\factorize{90}\displayfactorization
\factorize{112}\displayfactorization
\factorize{612}\displayfactorization
\factorize{7875}\displayfactorization
\factorize{22230}\displayfactorization
\factorize{1073741824}\displayfactorization
\factorize{2147483644}\displayfactorization
\factorize{\xintiiPow 2{40}}\displayfactorization
\factorize{\xinttheiiexpr 2^37 * 3^23 * 17^13\relax}%
\displayfactorization
% two examples ending with a (somewhat) `big' prime,
\factorize{10968058712}\displayfactorization
\factorize{1689242184972}\displayfactorization

\factorize{\xinttheiiexpr 111^13 * 371^7 * 1271^35\relax}
\displayfactorization[.75\linewidth]

% \factorize{2147483647}% does not exhaust memory takes about 2s

% \clearpage

% about 6s total last time I tried :

% \def\factorizeanddisplay #1{%
%     \pdfresettimer
%     \factorize{#1}%
%     \edef\z{\the\pdfelapsedtime}%
%     (needed \xintRound{2}{\z/65536} seconds)
%     \displayfactorization
%     \par\medskip
% }

% \factorizeanddisplay{2147483642}
% \factorizeanddisplay{2147483643}
% \factorizeanddisplay{2147483644}
% \factorizeanddisplay{2147483645}
% \factorizeanddisplay{2147483646}
% \factorizeanddisplay{2147483647}
% \factorizeanddisplay{2147483648}
% \factorizeanddisplay{2147483649}
% \factorizeanddisplay{2147483650}
\end{document}

factorizations

大整数的示例:

big one


现在重复代码,连同代码一起以 OP 问题的格式生成树,使用pst-tree

这需要latex+dvips或者也可以使用xelatex

% COMPILE WITH LATEX+DVIPS

\documentclass[border=3pt,preview,varwidth,multi]{standalone}

\usepackage{pst-tree}
\psset{levelsep=1,treesep=1,nodesep=2pt}

\usepackage{xint}
\usepackage{xintexpr}

\catcode`\_ 11

% This code (non-expandable) produces
% {{}{}{N}} followed with successive braced triplets
% {{p}{k}{m}} where p is a prime factor of N, 
% k its exponent in N, and m is the result of dividing
% N by p^k and all previous powers of smaller primes
% So the last triplet has m=1

% The code uses package xint to be able to deal
% with numbers larger than the TeX limit of 2^{31}-1
% on count registers. 

\def\factorize#1{%
    \edef\factorize_N{#1}%
    \def\factorize_exp{0}%
    \edef\factors{{{}{}{\factorize_N}}}%
    \factorize_i
}

\def\factorize_i{%
    \xintiiifOdd{\factorize_N}%
      {\factorize_ii}%
      {\edef\factorize_exp{\xintInc{\factorize_exp}}%
       \edef\factorize_N  {\xintHalf{\factorize_N}}%
       \factorize_i}%
}

\def\factorize_ii{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{2}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {\def\factorize_M{3}%
       \def\factorize_exp{0}%
       \factorize_iii}%
}

\def\factorize_iii{%
    \xintAssign\xintiiDivision\factorize_N\factorize_M\to\factorize_Q\factorize_R
    \xintiiifSgn{\factorize_R}%
      {% never happens: remainder can not be negative
      }%
      {% case of vanishing remainder
       \edef\factorize_exp{\xintInc{\factorize_exp}}%
       \let\factorize_N\factorize_Q 
       \factorize_iii
      }%
      {\factorize_iv}% 
}

\def\factorize_iv{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{\factorize_M}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {% here N>1, N=QM+R (0<R<Q) is < M(Q+1) and N has no prime factors
       % at most equal to M. If a prime P>M divides N, the
       % quotient N/P will be < Q+1, hence at most Q. If Q<=M, then
       % N/P must be 1 else there would be some prime <=M dividing N.
       % no \xintiiifGeq ...
       % \xintiifCmp will have branches for each of <, =, >, less convenient
       % So we use \xintiiifLt which exists, and permute the branches
       % compared to original code
       \xintiiifLt\factorize_M\factorize_Q
         {% we go on testing with bigger factors
          % or \edef\factorize_M{\xintInc{\xintInc{\factorize_M}}} perhaps
          \edef\factorize_M{\xintiiAdd \factorize_M 2}%
          \def\factorize_exp{0}%
          \factorize_iii
         }%
         {% implies that N is prime
          \edef\factors{\factors{{\factorize_N}{1}{1}}}% we stop here
         }%
      }%
}

\catcode`\_ 8

%% We now define the macro \FactorTree which will produce a tree
%% displaying the factorization, using PSTricks


\newtoks\FactorTreeA
\newtoks\FactorTreeB

\makeatletter

\newcommand*{\FactorsToTree}[1]{%
    \FactorsToTree@ #1%
}

% macro which was used to produce the images; variant follows which skips the
% exponents equal to 1.

% \newcommand*{\FactorsToTree@}[3]{%
%     \xintSgnFork{\xintCmp{#3}{1}}% check to see if end has been reached
%     {}%
%     {\FactorTreeA\expandafter{\the\FactorTreeA
%                               \Tcircle{${#1}^{#2}$}%
%                               \TR{1}%
%                               }}%
%     {\FactorTreeA\expandafter{\the\FactorTreeA 
%                              \Tcircle{${#1}^{#2}$}%
%                              \psTree{\TR{#3}}}%
%      \FactorTreeB\expandafter{\the\FactorTreeB \endpsTree}}%
% }


% This variant will not print the exponents equal to 1:

\newcommand*{\FactorsToTree@}[3]{%
    \ifnum 0#2=1 % first triplet has an empty #2, hence the trick with 0
       \expandafter\@firstoftwo
    \else
       \expandafter\@secondoftwo
    \fi
    % exponent #2 is 1, so don't print it
    {\xintSgnFork{\xintCmp{#3}{1}}% check to see if end has been reached
    {}%
    {\FactorTreeA\expandafter{\the\FactorTreeA
                              \Tcircle{${#1}$}%
                              \TR{1}%
                              }}%
    {\FactorTreeA\expandafter{\the\FactorTreeA 
                             \Tcircle{${#1}$}%
                             \psTree{\TR{#3}}}%
     \FactorTreeB\expandafter{\the\FactorTreeB \endpsTree}}}
    % exponent #2 is > 1 (or absent in the {}{}{N} triplet)
    {\xintSgnFork{\xintCmp{#3}{1}}% check to see if end has been reached
    {}%
    {\FactorTreeA\expandafter{\the\FactorTreeA
                              \Tcircle{${#1}^{#2}$}%
                              \TR{1}%
                              }}%
    {\FactorTreeA\expandafter{\the\FactorTreeA 
                             \Tcircle{${#1}^{#2}$}%
                             \psTree{\TR{#3}}}%
     \FactorTreeB\expandafter{\the\FactorTreeB \endpsTree}}}%
}


\newcommand*{\FactorTree}[1]{%
    \factorize{#1}%
    \FactorTreeA{\@gobbletwo}%
    \FactorTreeB{}%
    \xintApplyUnbraced\FactorsToTree{\factors}%
    \the\FactorTreeA\the\FactorTreeB
}

\makeatother


\begin{document}

%% \preview\FactorTree{1}\endpreview  %% (ok)

\preview\FactorTree{13}\endpreview

\preview\FactorTree{36}\endpreview

\preview\FactorTree{90}\endpreview

\preview\FactorTree{112}\endpreview

\preview\FactorTree{612}\endpreview

\preview\FactorTree{7875}\endpreview

\preview\FactorTree{22230}\endpreview

\preview\FactorTree{1073741824}\endpreview

\preview\FactorTree{2147483644}\endpreview

\preview\FactorTree{\xintiiPow 2{40}}\endpreview

\preview\FactorTree{\xinttheiiexpr 2^37 * 3^23 * 17^13\relax}%
\endpreview
% two examples ending with a (somewhat) `big' prime,

\preview\FactorTree{10968058712}\endpreview

\preview\FactorTree{1689242184972}\endpreview

\end{document}

内联产品分解的代码:

% The command \FactorizeInline produces (for math mode, at it uses \times) the
% product decomposition of its argument into prime powers, the exponents equal
% to 1 are not printed. The argument is supposed to be an integer > 1
% (arbitrarily big, but computation times will be large if it is not a product
% of reasonably small primes).
% $N = \FactorizeInline{N}$

\makeatletter
\def\@factorinliner  #1{\@factorinliner@ #1}
\def\@factorinliner@ #1#2#3{\ifnum #2>1 \expandafter\@firstoftwo\else
                                        \expandafter\@secondoftwo\fi
                            {{#1}^{#2}}{#1}}
\newcommand*{\FactorizeInline}[1]{%
    \factorize{#1}% 
    \xintListWithSep\times
            {\xintApply\@factorinliner{\expandafter\@gobble\factors}}%
}%
\makeatother

$13=\FactorizeInline{13}$

$36=\FactorizeInline{36}$

$90=\FactorizeInline{90}$

$112=\FactorizeInline{112}$

$612=\FactorizeInline{612}$

$7875=\FactorizeInline{7875}$

$22230=\FactorizeInline{22230}$

$1073741824=\FactorizeInline{1073741824}$

$2147483642=\FactorizeInline{2147483642}$

% $2147483643=\FactorizeInline{2147483643}$ % 4.5 seconds on my laptop

$2147483644=\FactorizeInline{2147483644}$

$2147483645=\FactorizeInline{2147483645}$

% $2147483646=\FactorizeInline{2147483646}$

% $2147483647=\FactorizeInline{2147483647}$ % 8 seconds on my 2012 laptop

$2147483648=\FactorizeInline{2147483648}$

% $2147483649=\FactorizeInline{2147483649}$ % 4.5 seconds on my laptop

$2147483650=\FactorizeInline{2147483650}$

% $19928968819=\FactorizeInline{19928968819}$ % 25 seconds on my 2012 laptop

$\xintiiPow 2{40} = \FactorizeInline{\xintiiPow 2{40}}$

% two examples ending with a (somewhat) `big' prime,

$10968058712=\FactorizeInline{10968058712}$

$1689242184972=\FactorizeInline{1689242184972}$

%\xinttheiiexpr 2^37 * 3^23 * 17^13\relax

$128154740640622513993964746937443811328=\FactorizeInline{128154740640622513993964746937443811328}$

factorize-inline


使用以下代码制作树木forest

\documentclass[border=3pt,varwidth,multi={forest}]{standalone}

\usepackage{calc} % for \widthof

\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{forest}

\usepackage{xint}
\usepackage{xintexpr}


%  macro \factorize as above
\catcode`\_ 11

% This code (non-expandable) produces
% {{}{}{N}} followed with successive braced triplets
% {{p}{k}{m}} where p is a prime factor of N, 
% k its exponent in N, and m is the result of dividing
% N by p^k and all previous powers of smaller primes
% So the last triplet has m=1

% The code uses package xint to be able to deal
% with numbers larger than the TeX limit of 2^{31}-1
% on count registers. 


\def\factorize#1{%
    \edef\factorize_N{#1}%
    \def\factorize_exp{0}%
    \edef\factors{{{}{}{\factorize_N}}}%
    \factorize_i
}

\def\factorize_i{%
    \xintiiifOdd{\factorize_N}%
      {\factorize_ii}%
      {\edef\factorize_exp{\xintInc{\factorize_exp}}%
       \edef\factorize_N  {\xintHalf{\factorize_N}}%
       \factorize_i}%
}

\def\factorize_ii{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{2}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {\def\factorize_M{3}%
       \def\factorize_exp{0}%
       \factorize_iii}%
}

\def\factorize_iii{%
    \xintAssign\xintiiDivision\factorize_N\factorize_M\to\factorize_Q\factorize_R
    \xintiiifSgn{\factorize_R}%
      {% never happens: remainder can not be negative
      }%
      {% case of vanishing remainder
       \edef\factorize_exp{\xintInc{\factorize_exp}}%
       \let\factorize_N\factorize_Q 
       \factorize_iii
      }%
      {\factorize_iv}% 
}

\def\factorize_iv{%
    \xintiiifZero{\factorize_exp}%
      {}%
      {\edef\factors{\factors{{\factorize_M}{\factorize_exp}{\factorize_N}}}}%
    \xintiiifOne{\factorize_N}%
      {}%
      {% here N>1, N=QM+R (0<R<Q) is < M(Q+1) and N has no prime factors
       % at most equal to M. If a prime P>M divides N, the
       % quotient N/P will be < Q+1, hence at most Q. If Q<=M, then
       % N/P must be 1 else there would be some prime <=M dividing N.
       % no \xintiiifGeq ...
       % \xintiifCmp will have branches for each of <, =, >, less convenient
       % So we use \xintiiifLt which exists, and permute the branches
       % compared to original code
       \xintiiifLt\factorize_M\factorize_Q
         {% we go on testing with bigger factors
          % or \edef\factorize_M{\xintInc{\xintInc{\factorize_M}}} perhaps
          \edef\factorize_M{\xintiiAdd \factorize_M 2}%
          \def\factorize_exp{0}%
          \factorize_iii
         }%
         {% implies that N is prime
          \edef\factors{\factors{{\factorize_N}{1}{1}}}% we stop here
         }%
      }%
}

\catcode`\_ 8

%% We now define the macro \FactorTree which will produce a tree
%% displaying the factorization, 
%% using TikZ+forest (for the bracket syntax, much easier to deal with compared
%% to the braces-based child-node native TikZ tree syntax)


\makeatletter

\newtoks\FactorTreeA
\newtoks\FactorTreeB

\newcommand*{\FactorsToTree@}[3]{%
    \ifnum #2=1 % 
       \expandafter\@firstoftwo
    \else
       \expandafter\@secondoftwo
    \fi
    % exponent #2 is 1, so don't print it
    {\xintSgnFork{\xintCmp{#3}{1}}% check to see if end has been reached
    {}%
        % here, this is the last triplet and it has the shape {P}{1}{1}
        % and P was already inserted as tree node in the previous step
        % and the forest syntax allows to insert options here
    {\FactorTreeA\expandafter{\the\FactorTreeA ,draw,circle}}%
    {\FactorTreeA\expandafter{\the\FactorTreeA 
                             [{${#1}$}]
                             [{${#3}$}%
                             }%
     \FactorTreeB\expandafter{\the\FactorTreeB ]}%
    }}%
    % exponent #2 is > 1
    {\xintSgnFork{\xintCmp{#3}{1}}% check to see if end has been reached
    {}%
    {\FactorTreeA\expandafter{\the\FactorTreeA
                              [{${#1}^{#2}$}]
                              %[1]%
                              }%
    }%
    {\FactorTreeA\expandafter{\the\FactorTreeA 
                             [{${#1}^{#2}$}]
                             [{$#3$}%
                             }%
     \FactorTreeB\expandafter{\the\FactorTreeB ]}%
    }}%
}

\newcommand*{\FactorsToTree}[1]{\FactorsToTree@ #1}

% for factors displayed inline 

\def\@factorinliner  #1{\@factorinliner@ #1}
\def\@factorinliner@ #1#2#3{\ifnum #2>1 \expandafter\@firstoftwo\else
                                        \expandafter\@secondoftwo\fi
                            {{#1}^{#2}}{#1}}
\def\FactorsInline{%
    \xintListWithSep\times
             {\xintApply\@factorinliner{\expandafter\@gobble\factors}}%
}

\newlength{\horizontalshift}  % for positioning of the edges from the tree top
\newsavebox{\NandFactors}

\newcommand*{\FactorTree}[1]{%
    \factorize{#1}%
    \sbox{\NandFactors}{$#1=\FactorsInline$}%
    \setlength{\horizontalshift}{(\wd\NandFactors-\widthof{$#1$})/2}%
    \FactorTreeA{}%
    \FactorTreeB{}%
    \bracketset{action character=@}%
    \xintApplyUnbraced\FactorsToTree{\expandafter\@gobble\factors}%
    \begin{forest}
      for tree={edge path={\noexpand\path [\forestoption{edge}]
                                (!u.south)--(.child anchor);}},
      where={level()==1}
        {edge path= {\noexpand\path [\forestoption{edge}]
            ($(!u.south)-(\the\horizontalshift,0cm)$)--(.child anchor);}}{},
      where={n()==1}{draw,circle}{},
      [{\box\NandFactors}, right=\horizontalshift,
      @\the\FactorTreeA
      @\the\FactorTreeB
      ]
    \end{forest}
}

\makeatother



\begin{document}

\FactorTree{13}

\FactorTree{36}

\FactorTree{90}

\FactorTree{112}

\FactorTree{612}

\FactorTree{7875}

\FactorTree{22230}

\FactorTree{1073741824}

\FactorTree{2147483644}

\FactorTree{\xintiiPow 2{40}}

\FactorTree{\xinttheiiexpr 2^37 * 3^23 * 17^13\relax}%

% two examples ending with a (somewhat) `big' prime,

\FactorTree{10968058712}

\FactorTree{1689242184972}

\end{document}

答案2

一个基本的forest基于 /count 的实现。

尽管forest提供了用于评估内容的键并且具有基本if键,但我使用了评估所有内容的宏。由于它依赖于计数,我认为它不能与forest的键一起使用,因为它们使用pgfmath。(它遭受的典型问题是它使用 TeX 的 dimen 寄存器,该寄存器不能大于 18,000 多;使用fp包和 TikZ 的fixedpointarithmetic库可以扩展它。)

可表示的最大数字是 2 147 483 644 ( 2^31-4),下一个整数 2 147 483 645 ( 2^31-3) 失败。

该算法效率不高。
对于输入数字,因子 2, 3, 5, 7, 9, …, 2n+ 1 直到/2 被检查是否能整除无剩余。

代码中包含一些关于该算法的注释。

\num包中的宏用于siunitx排版数字(甚至指数,尽管它们不能大于 30)。

代码

\documentclass[tikz]{standalone}
\usepackage{forest,mathtools,siunitx}
\makeatletter
\def\ifNum#1{\ifnum#1\relax
  \expandafter\pgfutil@firstoftwo\else
  \expandafter\pgfutil@secondoftwo\fi}
\forestset{
  num content/.style={
    delay={
      content/.expanded={\noexpand\num{\forestoption{content}}}}},
  pt@prime/.style={draw, circle},
  pt@start/.style={},
  pt@normal/.style={},
  start primeTree/.style={%
    /utils/exec=%
      % \pt@start holds the current minimum factor, we'll start with 2
      \def\pt@start{2}%
      % \pt@result will hold the to-be-typeset factorization, we'll start with
      % \pgfutil@gobble since we don't want a initial \times
      \let\pt@result\pgfutil@gobble
      % \pt@start@cnt holds the number of ^factors for the current factor
      \def\pt@start@cnt{0}%
      % \pt@lStart will later hold "l"ast factor used
      \let\pt@lStart\pgfutil@empty,
    alias=pt-start,
    pt@start/.try,
    delay={content/.expanded={$\noexpand\num{\forestove{content}}
                            \noexpand\mathrlap{{}= \noexpand\pt@result}$}},
    primeTree},
  primeTree/.code=%
    % take the content of the node and save it in the count
    \c@pgf@counta\forestove{content}\relax
    % if it's 2 we're already finished with the factorization
    \ifNum{\c@pgf@counta=2}{%
      % add the factor
      \pt@addfactor{2}%
      % finalize the factorization of the result
      \pt@addfactor{}%
      % and set the style to the prime style
      \forestset{pt@prime/.try}%
    }{%
      % this simply calculates content/2 and saves it in \pt@end
      % this is later used for an early break of the recursion since no factor
      % can be greater then content/2 (for integers of course)
      \edef\pt@content{\the\c@pgf@counta}%
      \divide\c@pgf@counta2\relax
      \advance\c@pgf@counta1\relax % to be on the safe side
      \edef\pt@end{\the\c@pgf@counta}%
      \pt@do}}

%%% our main "function"
\def\pt@do{%
  % let's test if the current factor is already greather then the max factor
  \ifNum{\pt@end<\pt@start}{%
    % great, we're finished, the same as above
    \expandafter\pt@addfactor\expandafter{\pt@content}%
    \pt@addfactor{}%
    \def\pt@next{\forestset{pt@prime/.try}}%
  }{%
    % this calculates int(content/factor)*factor
    % if factor is a factor of content (without remainder), the result will
    % equal content. The int(content/factor) is saved in \pgf@temp.
    \c@pgf@counta\pt@content\relax
    \divide\c@pgf@counta\pt@start\relax
    \edef\pgf@temp{\the\c@pgf@counta}%
    \multiply\c@pgf@counta\pt@start\relax
    \ifNum{\the\c@pgf@counta=\pt@content}{%
      % yeah, we found a factor, add it to the result and ...
      \expandafter\pt@addfactor\expandafter{\pt@start}%
      % ... add the factor as the first child with style pt@prime
      % and the result of int(content/factor) as another child.
      \edef\pt@next{\noexpand\forestset{%
        append={[\pt@start, pt@prime/.try]},
        append={[\pgf@temp, pt@normal/.try]},
        % forest is complex, this makes sure that for the second child, the
        % primeTree style is not executed too early (there must be a better way).
        delay={
          for descendants={
            delay={if n'=1{primeTree, num content}{}}}}}}%
    }{%
      % Alright this is not a factor, let's get the next factor
      \ifNum{\pt@start=2}{%
        % if the previous factor was 2, the next one will be 3
        \def\pt@start{3}%
      }{%
        % hmm, the previos factor was not 2,
        % let's add 2, maybe we'll hit the next prime number
        % and maybe a factor
        \c@pgf@counta\pt@start
        \advance\c@pgf@counta2\relax
        \edef\pt@start{\the\c@pgf@counta}%
      }%
      % let's do that again
      \let\pt@next\pt@do
    }%
  }%
  \pt@next
}

%%% this builds the \pt@result macro with the factors
\def\pt@addfactor#1{%
  \def\pgf@tempa{#1}%
  % is it the same factor as the previous one
  \ifx\pgf@tempa\pt@lStart
    % add 1 to the counter
    \c@pgf@counta\pt@start@cnt\relax
    \advance\c@pgf@counta1\relax
    \edef\pt@start@cnt{\the\c@pgf@counta}%
  \else
    % a new factor! Add the previous one to the product of factors
    \ifx\pt@lStart\pgfutil@empty\else
      % as long as there actually is one, the \ifnum makes sure we do not add ^1
      \edef\pgf@tempa{\noexpand\num{\pt@lStart}\ifnum\pt@start@cnt>1 
                                           ^{\noexpand\num{\pt@start@cnt}}\fi}%
      \expandafter\pt@addfactor@\expandafter{\pgf@tempa}%
    \fi
    % setup the macros for the next round
    \def\pt@lStart{#1}% <- current (new) factor
    \def\pt@start@cnt{1}% <- first time
  \fi
}
%%% This simply appends "\times #1" to \pt@result, with etoolbox this would be
%%% \appto\pt@result{\times#1}
\def\pt@addfactor@#1{%
  \expandafter\def\expandafter\pt@result\expandafter{\pt@result \times #1}}

%%% Our main macro:
%%% #1 = possible optional argument for forest (can be tikz too)
%%% #2 = the number to factorize
\newcommand*{\PrimeTree}[2][]{%
  \begin{forest}%
    % as the result is set via \mathrlap it doesn't update the bounding box
    % let's fix this:
    tikz={execute at end scope={\pgfmathparse{width("${}=\pt@result$")}%
                         \path ([xshift=\pgfmathresult pt]pt-start.east);}},
    % other optional arguments
    #1
    % And go!
    [#2, start primeTree]
  \end{forest}}
\makeatother
\begin{document}
\PrimeTree{36}
\PrimeTree{90}
\PrimeTree{112}
\PrimeTree{612}
\PrimeTree{7875}
\PrimeTree{22230}
\PrimeTree{1073741824}
\PrimeTree{2147483644}
\end{document}

输出

enter image description hereenter image description hereenter image description here

enter image description hereenter image description here enter image description hereenter image description here

enter image description here

答案3

这是答案的一半,它只是分解数字。TeX 是图灵完备的,不需要额外的软件包。:-) 我其实没心情看pst-tree,所以我会跳过后半部分。此外,@Qrrbrbirlbel 的答案(我投了赞成票)很好地涵盖了这一点。如果出于某种原因,有人更喜欢我的代码,那么应该很容易用生成树所需的任何东西来修补我拥有的通用因子处理宏。

我使用的算法非常简单:它检查 2 和 3,然后检查所有 6k-1 或 6k+1 的数字,直到 n 的平方根。它应该可以处理任意长的数字(最多 2^31,TeX 对计数器的限制),前提是它在递归时不会耗尽 TeX 的内存。例如,当你给它 2^31-1 时就会发生这种情况,而这恰好是梅森素数。

\documentclass[12pt]{article}

\makeatletter

\newcount\factorize@n  % the number to be factorized
\newcount\factorize@t  % temporary
\newcount\factorize@p  % a candidate factor
\newcount\factorize@c  % counter of factors

% machinery for factorization
%
\def\factorize#1{%
  \factorize@begin{#1}%
  \factorize@n=#1
  \factorize@c=0
  \factorize@p=2
  \factorize@try%
  \factorize@p=3
  \factorize@try%
  \factorize@p=5
  \factorize@loop%
  \ifnum\factorize@c>0%
    \ifnum\factorize@n>1%
      \factorize@process{\the\factorize@n}%
    \fi%
  \else%
    \factorize@process{\the\factorize@n}%
  \fi%
  \factorize@end{#1}%
}
\def\factorize@loop{%
  \factorize@t=\factorize@p
  \multiply\factorize@t by \factorize@p
  \ifnum\factorize@t>\factorize@n\else%
    \factorize@try%
    \advance\factorize@p by 2
    \factorize@t=\factorize@p
    \multiply\factorize@t by \factorize@p
    \ifnum\factorize@t>\factorize@n\else%
      \factorize@try%
      \advance\factorize@p by 4
      \factorize@loop%
    \fi%
  \fi%
}

\def\factorize@try{%
  \factorize@t=\factorize@n
  \divide\factorize@t by \factorize@p
  \multiply\factorize@t by \factorize@p
  \ifnum\factorize@n=\factorize@t%
    \factorize@process{\the\factorize@p}%
    \divide\factorize@n by \factorize@p
    \advance\factorize@c by 1
    \factorize@try%
  \fi%
}

% Stubs to be called at start, end, and when a factor is found
%
\def\factorize@begin#1{%
  \noindent%
  $#1 =%$
}
\def\factorize@end#1{%
  $%$
  \par%
}
\def\factorize@process#1{%
  \ifnum\factorize@c>0%
    \times%
  \fi%
  #1%
}

\makeatother

% Demo
%
\begin{document}
  \factorize{42}
  \factorize{5040}
  \factorize{1234567890}
  %\factorize{2147483647} exhausts TeX's memory
\end{document}

微小的变化会将大于一的多重因素组合在一起。

\documentclass[12pt]{article}

\makeatletter

\newcount\factorize@n  % the number to be factorized
\newcount\factorize@t  % temporary
\newcount\factorize@p  % a candidate factor
\newcount\factorize@c  % counter of factors (total)
\newcount\factorize@w  % counter of factors (power of given candidate)

% machinery for factorization
%
\def\factorize#1{%
  \factorize@begin{#1}%
  \factorize@n=#1
  \factorize@c=0
  \factorize@p=2
  \factorize@try%
  \factorize@p=3
  \factorize@try%
  \factorize@p=5
  \factorize@loop%
  \ifnum\factorize@c>0
    \ifnum\factorize@n>1
      \factorize@process{\the\factorize@n}{1}%
    \fi%
  \else%
    \factorize@process{\the\factorize@n}{1}%
  \fi%
  \factorize@end{#1}%
}
\def\factorize@loop{%
  \factorize@t=\factorize@p
  \multiply\factorize@t by \factorize@p
  \ifnum\factorize@t>\factorize@n\else%
    \factorize@try%
    \advance\factorize@p by 2
    \factorize@t=\factorize@p
    \multiply\factorize@t by \factorize@p
    \ifnum\factorize@t>\factorize@n\else%
      \factorize@try%
      \advance\factorize@p by 4
      \factorize@loop%
    \fi%
  \fi%
}
\def\factorize@try{%
  \factorize@w=0
  \factorize@try@aux%
  \ifnum\factorize@w>0
    \factorize@process{\the\factorize@p}{\the\factorize@w}%
    \advance\factorize@c by \factorize@w
  \fi%
}
\def\factorize@try@aux{%
  \factorize@t=\factorize@n
  \divide\factorize@t by \factorize@p
  \multiply\factorize@t by \factorize@p
  \ifnum\factorize@n=\factorize@t
    \divide\factorize@n by \factorize@p
    \advance\factorize@w by 1
    \factorize@try@aux%
  \fi%
}

% Stubs to be called at start, end, and when a factor is found
%
\def\factorize@begin#1{%
  \noindent%
  $#1 =%$
}
\def\factorize@end#1{%
  $%$
  \par%
}
\def\factorize@process#1#2{%
  \ifnum\factorize@c>0
    \times%
  \fi%
  \ifnum#2>1
    #1^{#2}%
  \else%
    #1%
  \fi%
}

\makeatother

% Demo
%
\begin{document}
  \factorize{42}
  \factorize{5040}
  \factorize{1234567890}
  %\factorize{2147483647} exhausts TeX's memory
\end{document}

答案4

稍微不同的方法是将 LaTeX 的排版与其他编程语言的功能相结合。与其他解决方案相比,代码几乎可以立即执行,对外行来说相对可读,而且更短。

这里使用了基于 greatpythontex包和forest绘制树的包的 Python。Python 还提供了几个用于数论的复杂包,因此还可以使用更高级的算法。代码有点乱,因为我将森林包的字符串创建压缩到了分解算法中。

\documentclass{article}

\usepackage{tikz}
\usepackage{forest}
\usepackage{pythontex}


\begin{pycode}
from math import sqrt

def generate_tree(number):
        global tree_text
        tree_text = ""
        def prime_factors_recursive(n, level): 
                """Finds the prime factors of 'n' and generates text representation
                     according to tikz forest package.
                """ 
                limit = int(sqrt(n)) + 1
                divisor = 2
                num = n
                level += 1
                global tree_text
                tree_text = tree_text + "["
                for divisor in range(2, limit): 
                        if (num % divisor == 0): 
                                num /= divisor 
                                tree_text = tree_text + "%d [%d,circle,draw] " %(n, divisor)
                                return (n, (divisor, prime_factors_recursive(num, level)))
                tree_text = tree_text + "%d,circle,draw" %(n)
                for i in range(level):
                        tree_text = tree_text + "]"
                return (n,)

        prime_factors_recursive(number, 0)
        output = r'\begin{forest}' + tree_text + r'\end{forest}'
        return output

\end{pycode}

\newcommand{\PrimeTree}[1]{%
\py{generate_tree(#1)}
}

\begin{document}
\PrimeTree{36}
\PrimeTree{90}
\PrimeTree{112}
\PrimeTree{612}
\PrimeTree{7875}
\PrimeTree{22230}
\PrimeTree{19928968819}

\end{document}

enter image description here

相关内容