edit (2017/09/01 & 02):
Release 1.2o deprecates some macros which were used here, so the answer was updated. On this occasion I replaced uses of \if...\else...\fi with the xint provided \xintiiifOne etc... which safely select a branch à la firstoftwo/secondoftwo way and avoid things like \expandafter\expandafter\expandafter at user level.
Note: the xint manual also contains code implementing expandably Rabin-Miller strong pseudo-primality tests...
This answer has evolved in stages. New contributions were added at the bottom (apart from the images which I put on top).
macro \factorize to produce programmatically the factorization of input N. The output is put in macro \factors. For example for N=36, \factors expands to {{}{}{36}}{{2}{2}{9}}{{3}{2}{1}}. Each successive triplet is {p}{k}{m} where p^k is the p-factor of N, and m the result of dividing N by it and all previous ones. The first triple {}{}{N} is a bit of a nuisance, and this explains \expandafter\@gobble\factors in some the displaying codes. Initially the displays used tabulars.
then I added code using pst-tree to produce the trees from the result available in \factors. I also added code for just printing the factorization inline.
I now add code using TikZ+forest, which I have learned a bit since seeing it used beautifully in Qrrbrbirlbel's answer. The code for the forest tree also incoporates the inline version of the factorization.
I use pst-tree and forest only to display, not to compute the factorization. Both pst-tree and forest syntax for the trees allowed a simple approach to work from \factors to the trees: two token lists are filled-up step by step; if using the native TikZ syntax with child, that would be much more difficult because of braces { and }.
Images of trees produced with forest:
Images of trees using pst-tree (as were done manually by PSTikZ.) Here are some samples (the code also has the variant to not display the 1's when they are exponents). For some other ways to do trees, e.g with TikZ's childs and nodes, the \factors macro prepared by the \factorize command should probably be done in a slightly different manner.
I too propose half of an answer using package xint for the arithmetic computations (on arbitrarily big numbers). The command \factorize{N} results in macro \factors containing a list of triplets {p}{k}{m}, where p is a prime number showing up in the factorization, k is its exponent, m is the result of division of N by p^k as well as all previous factors corresponding to smaller primes. So the last triplet has m=1, and the first is {}{}{N}.
The tree could then be constructed from this macro \factors; here I just have a \displayfactorization to display the result using tabulars (and I use some macros of xint to transform \factors into what goes into the tabular). There is an optional argument to set up the width of the second column.
I use the numprint package to print very long numbers without going beyond the page physical limits.
The algorithm is very lame: first divisions by 2 are tested, then 3, then 5, and all successive odd integers until N has been reduced to 1.
There is no impact on TeX memory, apart from \factors being filled up.
The algorithm would be of course faster if done using only TeX \count registers (and eTeX \numexpr for convenience), but this would restrict it to numbers < 2^{31}.
update: I have incorporated the usual halting test to not go beyond square root of n, makes the thing a bit more efficient when the factorization ends in a 'big' prime (two such examples added).
\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}
and an example with big integers:
And now the code repeated, together with code to produce trees in the format of the OP question, using pst-tree:
This resuires latex+dvips or can also use 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}
Code for inline product decomposition:
% 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}$
Code for doing the trees with 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}
