I am trying to make tree diagram of prime factorization like this

![image.png](/image?hash=0e425cd7aac98d79152b2181c9e1e80b89d557b847acc426d8244e4cf3290ab2)

How to automatically draw tree diagram of prime factorization with LaTeX?
Prime numbers are quite expensive in computation. The following is far from perfectly optimized, but should implement code performing not too badly.

In particular it implements the following handy functions:


\primetree_if_is_prime:nTF { <num> } { <true> } { <false> }


checks whether <num> is a prime or not and branches accordingly. It uses a few reasonable optimizations:

1. get the cases 0 and 1 done with a single comparison
2. get the cases 2 and 3 done with another comparison
3. use a big step-size (6) instead of just 2, leaving out all the odd numbers dividable by 3 (for which we explicitly test) (this is true since the odd numbers stepped over can be calculated as 5 + 6*n* + 4).
4. only loop until the test-number is bigger than the square root

The next function implemented is


\primetree_next_prime:n { <num> }

which expands to a prime bigger than <num>.

With these two we can build a table quite comfortably. If the number is a prime we're done, else check whether it's dividable by our current prime, if so do that, else find the next prime, loop.


\documentclass{article}

\ExplSyntaxOn
\NewDocumentCommand \primetree { m }
{
\begin { tabular } { r | r }
\primetree:nn {2} {#1}
\end { tabular }
}
\prg_new_conditional:Npnn \primetree_if_is_prime:n #1 { TF, T }
{
\int_compare:nNnT {#1} < 2 { \prg_break:n { \use_i:nn \prg_return_false: } }
\int_compare:nNnT {#1} < 4 { \prg_break: }
\int_compare:nNnT { \int_mod:nn {#1} 2 } = \c_zero_int
{ \prg_break:n { \use_i:nn \prg_return_false: } }
\int_compare:nNnT { \int_mod:nn {#1} 3 } = \c_zero_int
{ \prg_break:n { \use_i:nn \prg_return_false: } }
\exp_args:Nnne \__primetree_if_is_prime:nnn
{5} {#1} { \fp_eval:n { round(sqrt(#1)) } }
\prg_break_point:
\prg_return_true:
}
\cs_new:Npn \__primetree_if_is_prime:nnn #1#2#3
{
\int_compare:nNnT {#1} > {#3} { \prg_break: }
\int_compare:nNnT { \int_mod:nn {#2} {#1} } = \c_zero_int
{ \prg_break:n { \use_i:nn \prg_return_false: } }
\int_compare:nNnT { \int_mod:nn {#2} { #1 + 2 } } = \c_zero_int
{ \prg_break:n { \use_i:nn \prg_return_false: } }
\exp_args:Ne \__primetree_if_is_prime:nnn
{ \int_eval:n { #1 + 6 } } {#2} {#3}
}
\cs_generate_variant:Nn \__primetree_if_is_prime:nnn { nne }
\cs_new:Npn \primetree_next_prime:n #1
{
\int_step_function:nnnN { #1 + 1 + (\int_mod:nn {#1} 2) } { 2 } \c_max_int
\__primetree_next_prime_aux:n
\use:n { \msg_expandable_error:nnn { primetree } { out-of-primes } {#1} }
}
\msg_new:nnn { primetree } { out-of-primes } { no~ next~ prime~ (#1). }
\cs_new:Npn \__primetree_next_prime_aux:n #1
{ \primetree_if_is_prime:nT {#1} { \prg_break:n { \use_i:nnn {#1} } } }
\cs_new:Npn \primetree:nn #1#2
{
\primetree_if_is_prime:nTF {#2}
{#2&#2\\1&}
{
\int_compare:nNnTF { \int_mod:nn {#2} {#1} } = \c_zero_int
{
#2 & #1 \\
\exp_args:Nne \primetree:nn {#1} { \int_eval:n {#2/#1} }
}
{ \exp_args:Ne \primetree:nn { \primetree_next_prime:n {#1} } {#2} }
}
}
\ExplSyntaxOff

\begin{document}
\primetree{108}

\primetree{99}

\primetree{65}

\primetree{70499}
\end{document}


![primefactor-1.png](/image?hash=5072d32b9511148e063cc4a87c2345a262ef37cf5c9a8765f65eab0e630f4956)

Enter question or answer id or url (and optionally further answer ids/urls from the same question) from

Separate each id/url with a space. No need to list your own answers; they will be imported automatically.