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)