[Question]
  [
[Inspired by this question over at Mathematics](https://math.stackexchange.com/q/1775719/248583).
---
**The Problem**
> 
> Let `n` be a natural number `‚â• 2`. Take the biggest divisor of `n` ‚Äì which is different from `n` itself ‚Äì and subtract it from `n`. Repeat until you get `1`.
> 
> 
> 
**The Question**
*How many steps does it take to reach `1` for a given number `n ‚â• 2`.*
**Detailed Example**
> 
> Let `n = 30`.
> 
> 
> 
The greatest divisor of:
```
1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1
```
It takes *6 steps* to reach `1`.
**Input**
* Input is an integer `n`, where `n ‚â• 2`.
* Your program should support input up to the language's maximum integer value.
**Output**
* Simply output the number of steps, like `6`.
* Leading/trailing whitespaces or newlines are fine.
**Examples**
```
f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015
```
**Requirements**
* You can get input from `STDIN`, command line arguments, as function parameters or from the closest equivalent.
* You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so shortest answer in bytes wins.
* Standard loopholes are disallowed.
---
This series can be found on OEIS as well: **[A064097](https://oeis.org/A064097)**
> 
> A quasi-logarithm defined inductively by `a(1) = 0` and `a(p) = 1 + a(p-1)` if `p` is prime and `a(n*m) = a(n) + a(m)` if `m,n > 1`.
> 
> 
> 
  
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 9 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
√Ü·π™√êƒø√ÜFL‚Ç¨S
```
[Try it online!](http://jelly.tryitonline.net/#code=w4bhuarDkMS_w4ZGTOKCrFM&input=&args=MTU3MDQ3NzgxMTY1NzIzNzIxNzAzODQxMTUyMDYyMDM3MDQ1Nzc0MTQzMTkxNzExNTg0NDExOTM0MDg2MDgzNjM2NzA3Njc5NTM1MDgwMjQwMTY3Njg5MzM2ODk2OTkxMjExMjMyOTk3OTU5NjUzMzYxODIxNTI3MzA2OTYxODU4NjA5NTY3NjIyMjg5ODg4ODA2NTA1NTYyNTgzOTgzOTI5MDk1NDMyMTU3MzMwMjc1MzI5ODE2MzA3NzYxMzc4NTM4ODExMTY4MzgwNDIxNzY3NjMxMDk0NTcwMDAwNjQxMzY4MDE1NTgwMTcyNjc0MzQxNTkxMzY3Mzc4NTAxODE4OTM5NzIwMTA3OTk1NjE0MDE3MTgyNjg5MjIwOTQ2MTk0ODg0NzM0MTI1MjU0Mzk1MzE5NzQ0MDUyMDQyMDU4NDE5Njk0MzA1MTUwNTIyNzg3NzYwNDU4NjY0OTQ5NTIzNzc4OTYxMTA5MjQxNzUwOTg3NjA5OTkzNTc5NjE0NjU4NDk5MTE5ODczNzgyOTAxODYxNjg5MjU2ODYzODM4MTM2NjkyMTEwMTY5MTc0OTI0OTMxNTU5MTQ0MDE2NDE0MTU5MzU5NjYyNzUyMDIyNjU0Mzk5NjcyODM0NjEzNDU1MzMwMDg3OTIwMzQyNTg1NTM5NjU5NDMyOTg0NTc2) or [verify all test cases](http://jelly.tryitonline.net/#code=w4bhuarDkMS_w4ZGTOKCrFMKw4figqxH&input=&args=NSwgMzAsIDMxLCAzMiwgMTAwLCAyMDAsIDE1NzA0Nzc4MTE2NTcyMzcyMTcwMzg0MTE1MjA2MjAzNzA0NTc3NDE0MzE5MTcxMTU4NDQxMTkzNDA4NjA4MzYzNjcwNzY3OTUzNTA4MDI0MDE2NzY4OTMzNjg5Njk5MTIxMTIzMjk5Nzk1OTY1MzM2MTgyMTUyNzMwNjk2MTg1ODYwOTU2NzYyMjI4OTg4ODgwNjUwNTU2MjU4Mzk4MzkyOTA5NTQzMjE1NzMzMDI3NTMyOTgxNjMwNzc2MTM3ODUzODgxMTE2ODM4MDQyMTc2NzYzMTA5NDU3MDAwMDY0MTM2ODAxNTU4MDE3MjY3NDM0MTU5MTM2NzM3ODUwMTgxODkzOTcyMDEwNzk5NTYxNDAxNzE4MjY4OTIyMDk0NjE5NDg4NDczNDEyNTI1NDM5NTMxOTc0NDA1MjA0MjA1ODQxOTY5NDMwNTE1MDUyMjc4Nzc2MDQ1ODY2NDk0OTUyMzc3ODk2MTEwOTI0MTc1MDk4NzYwOTk5MzU3OTYxNDY1ODQ5OTExOTg3Mzc4MjkwMTg2MTY4OTI1Njg2MzgzODEzNjY5MjExMDE2OTE3NDkyNDkzMTU1OTE0NDAxNjQxNDE1OTM1OTY2Mjc1MjAyMjY1NDM5OTY3MjgzNDYxMzQ1NTMzMDA4NzkyMDM0MjU4NTUzOTY1OTQzMjk4NDU3Ng).
### Background
The definition of sequence [A064097](https://oeis.org/A064097) implies that
$$\small{a(p)-a(p-1)=1}\text{ for all primes }p\text{ and }a(km)=a(k)+a(m)\text{ for all }k,m\in \mathbb{N}$$
By [Euler's product formula](https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_product_formula)
$$\small{\varphi(n)=n\prod\_{p|n}\left(1-{1\over p}\right)=n\prod\_{p|n}{{p-1}\over p}}$$
where \$\varphi\$ denotes Euler's totient function and \$p\$ varies only over prime numbers.
Combining both, we deduce the property
$$\small{a(\varphi(n))=a\left(n\prod\_{p|n}{{p-1}\over p}\right)=a(n)+\sum\_{p|n}\left(a(p-1)-a(p)\right)=a(n)-\sum\_{p|n}{1=a(n)-\omega(n)}}$$
where \$\omega\$ denotes the number of distinct prime factors of \$n\$.
Applying the resulting formula \$k + 1\$ times, where \$k\$ is large enough so that \$\varphi^{k+1}(n)=1\$, we get
$$\small{
\begin{aligned}
0=a\left(\varphi^{k+1}(n)\right)=a\left(\varphi^k(n)\right)-\omega\left(\varphi^k(n)\right)&=a\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^k(n)\right) \\
&= \cdots = a(n)-\sum\_{j=0}^k\omega\left(\varphi^j(n)\right)
\end{aligned}
}$$
From this property, we obtain the formula
$$\small{a(n)=\sum\_{j=0}^k\omega\left(\varphi^j(n)\right)=\sum\_{j=0}^{+\infty}\omega\left(\varphi^j(n)\right)}$$
where the last equality holds because \$\omega(1)=0\$.
### How it works
```
√Ü·π™√êƒø√ÜFL‚Ç¨S  Main link. Argument: n
  √êƒø       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
√Ü·π™           Apply Euler's totient function.
           Since œÜ(1) = 1, This computes œÜ-towers until 1 is reached.
    √ÜF     Break each resulting integer into [prime, exponent] pairs.
      L‚Ç¨   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.
```
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), ~~13~~ 11 bytes
Code:
```
[D√í¬¶P-¬ºD#]¬æ
```
Explanation:
```
[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  √í          # Get the prime factors, in the form [2, 3, 5]
   ¬¶         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¬º      # Add one to the counting variable.
          ¬æ  # Push the counting variable and implicitly print that value.
```
Uses **CP-1252** encoding. [Try it online!](http://05ab1e.tryitonline.net/#code=W0TDksKmUC3CvEQjXcK-&input=MjAw).
[Answer]
# Pyth, 11 bytes
```
fq1=-Q/QhPQ
```
[Test suite](https://pyth.herokuapp.com/?code=fq1%3D-Q%2FQhPQ&test_suite=1&test_suite_input=5%0A30%0A31%0A32%0A100%0A200&debug=0)
A straightforward repeat-until-true loop.
Explanation:
```
fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.
```
[Answer]
# [Retina](https://github.com/mbuettner/retina/wiki/The-Language), 12
* 14 bytes saved thanks to @MartinB√ºttner
```
(1+)(?=\1+$)
```
This assumes [input given in unary](http://meta.codegolf.stackexchange.com/questions/5343/can-numeric-input-output-be-in-unary) and output given in decimal. If this is not acceptable then we can do this for 6 bytes more:
# [Retina](https://github.com/mbuettner/retina/wiki/The-Language), 18
* 8 bytes saved thanks to @MartinB√ºttner
```
.+
$*
(1+)(?=\1+$)
```
[Try it online - 1st line added to run all testcases in one go.](http://retina.tryitonline.net/#code=JShHYAouKwokKgooMSspKD89XDErJCk&input=NQozMAozMQozMgoxMDAKMjAw)
Sadly this uses unary for the calculations, so input of 2016155 is not practical.
* The first stage (2 lines) simply converts the decimal input to unary as a string of `1`s
* The second stage (1 line) calculates the largest factor of n using regex matching groups and lookbehinds to and effectively subtracts it from n. This regex will match as many times as is necessary to reduce the number as far as possible. The number of regex matches will be the number of steps, and is output by this stage.
[Answer]
## Python 2, ~~50~~ 49 bytes
```
f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)
```
This isn't going to finish that last test case any time soon...
Alternatively, here's a 48-byte which returns `True` instead of `1` for `n=2`:
```
f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 10 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
√Üf·∏äP·∫°¬µ√êƒøi2
```
[Try it online!](http://jelly.tryitonline.net/#code=w4Zm4biKUOG6ocK1w5DEv2ky&input=&args=MjAw) or [verify most test cases](http://jelly.tryitonline.net/#code=w4Zm4biKUOG6ocK1w5DEv2kyCsOH4oKsRw&input=&args=NSwgMzAsIDMxLCAzMiwgMTAwLCAyMDA). The last test cases finishes quickly locally.
### How it works
```
√Üf·∏äP·∫°¬µ√êƒøi2  Main link. Argument: n (integer)
√Üf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  ·∏ä         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ·∫°       Yield the abs. value of the difference of the divisor (or 1) and n.
     ¬µ      Convert the chain to the left into a link.
      √êƒø    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.
```
[Answer]
# Pyth - ~~15~~ ~~14~~ 13 bytes
Special casing `1` is really killing me.
```
tl.u-N/Nh+PN2
```
[Try it online here](http://pyth.herokuapp.com/?code=tl.u-N%2FNh%2BPN2&test_suite=1&test_suite_input=5%0A30%0A31%0A32%0A100%0A200&debug=0).
```
tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1
```
[Answer]
# Julia, ~~56~~ ~~50~~ ~~45~~ 39 bytes
```
f(n)=n>1&&f(n-n√∑first(factor(n))[1])+1
```
This is a recursive function that accepts an integer and returns an integer.
Ungolfed:
```
function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n √∑ first(factor(n))[1]) + 1
    end
end
```
[Try it online!](http://julia.tryitonline.net/#code=ZihuKT1uPjEmJmYobi1uw7dmaXJzdChmYWN0b3IobikpWzFdKSsxCgpmb3IgdGVzdCBpbiBbKDUsMyksICgzMCw2KSwgKDMxLDcpLCAoMzIsNSksICgxMDAsOCksICgyMDAsOSksIChiaWcoMjAxNileMTU1LDIwMTUpXQogICAgcHJpbnRsbihmKHRlc3RbMV0pID09IHRlc3RbMl0pCmVuZA&input=) (includes all test cases)
Saved 6 bytes thanks to Martin B√ºttner and 11 thanks to Dennis!
[Answer]
# JavaScript (ES6), ~~\*44~~ 38
*Edit* 6 bytes saved thanks @l4m2
(\* 4 striked is still 4)
Recursive function
```
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0
```
Less golfed
```
f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}
```
**Test**
```
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0
console.log=x=>O.textContent+=x+'\n';
[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
```
```
<pre id=O></pre>
```
[Answer]
# Regex `üêù` (ECMAScript or better), 12 bytes
```
(x+)(?=\1+$)
```
Takes its input in unary, as a sequence of `x` characters whose length represents the number. Returns its output as the number of matches.
This of course has already been done in [Digital Trauma's Retina answer](https://codegolf.stackexchange.com/a/79666/17216), but here it is demonstrated to work on a much wider variety of regex engines.
[Try it online!](https://tio.run/##TY@7TsMwFEB/JUSoubdp0hohhga3E0OXDjACg9XeOhccx7LdB32sfACfyI@EVgKJ@ZzhnDe1UWHh2cUiOF6Sb1r7Th@dl5a2ySPph50D2MvJsN/BLkeYyheRX2PXH@6xjO1T9Gw1YBkMLwjuBsUtDpJMZ1gFOaq2NRsCMNKTWhq2BIhX0q6NwYOWpgzOcISsOOu8ArBSl4asjjVObo5HDnM1B5ZO@UAzG0E/j14R/wD9B3YipmJ8wRhr327Tmd0ow8vEK6tpnKS5qVath4rvJVWc53hoZLpLS0@OVATGslFxUYM/l/d67rwV4TIhKreOIXrgPEu@P7@SLIdm2vx2jkeI1enUiUII8QM "JavaScript (SpiderMonkey) ‚Äì Try It Online") - ECMAScript  
[Try it online!](https://tio.run/##RY5BasMwEEX3OcUQhkjCdmwVuslYiQPptqvumiBSkwSBmriSCy5GXfYAPWIv4ipuoJth/ufP/NccnL0fXj8AHUFvL/XeAuYUpSo366f1MkyOF8fRq4LKJYkezDEq0TfOnFuYbs9TClBZ5RtrWs4ylvr3F9/GE51mMpXi8HYNrf7dIvpigVrQ9ZePjXtX2fJO9JV9ljsVZ7GjMAEYm83NQFOqMRC3JInhWnHWsQ6NUJ85uvxE6GezkWvEisyS/jDRzBn8fH0Dm1c1haD1w@NG64F3ieArtZUJimGQmZTyFw "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##bVLLbtswELz7K7ZCA5N@MFaPZYSgLVqgQJMWydHRgZYomw5FqeQqVmzk2g/oJ/ZH3JWsPgJEl9XuDmc5w92qBzXf5vdHU9aVR9hSLkwlJhL@rzRo7Is1r9e6pc6oblbWZJBZFQJcKePgAEMtoEIKD5XJoaQOu0Vv3BqUX4dlygE3vtoF@NhmukZT0ckRwCdjNRSJ07v@l0Uiq3ItqB9x@b4pCu11fqNVrj2setjzIvtzckgLzuUwN8xQ7jYdP2MhWZEGlX8xTjPOXyWusZabggWhvzfKBhadTyaTiPPDc@iJgTF8keBADPiXgQjOiWFFuHsZpsn4zo27iPLpVHv6phC1d@CT4Y/UlnU3IHBJbqyqymrlYJ8UxKgl3GbKOZJuXN0gJNCpHWrs9jGgLoVxXMKgs4eJjQrXukW6Zm8xwGCIpbsTxwnkCDFIHPrLFCy1O5QItTXIojk9AuER3II6nx3SGnhRKx80JcwuFymfgYtfbAqr3Ro3F2/gEjokvKUQp8SYbZRfpu2gp89cnEp45716DKIw1rJ2Nm7HvSkAReU7bXSNxC0kuIvExRSmUxJ4pTDbkEMlsXlRnjLWb66jBf9A5KeNETuvajaMyKr68Wtxo9xa06TFzHHaG7AVuZQlJb10aCwGxgnYkJbOhYLt@WB5Rf7tvEHNuifmcp@gb7rX@teuyVEsWHSWw68fP@Esj8inGWRcPtE36pbtyNopZ5fJXTx9zY/d8hzjeRzHvwE "Java (JDK) ‚Äì Try It Online") - Java  
[Try it online!](https://tio.run/##fVLBjtMwEL33KwbLUmyadhtOiDSqhOiiIthFoZzaynITpzF1nch2UdFqr3wAn8iPlEm6CwKtOMQaz3vz5skvbd2ep7O2boE6yIBcERhD69ROONUaWSgWXY2fz4SopQmiaA6tNsqt2Zqn6/zKRzFE@FXYFDvVEWxQNngmxPXi/VwIHkPCURKF04G2WngVGGkLp8ZbWeyDw0MYfdCBxEBGCeHp3yyniqPzurH/ZX25IBMEBlXjGNXZJKUmq9CUZ5@WbxY3POV3oCtGzcoHZ5TFio@STZaRtSUcyf64RQTb8SQeJbybV6fWNKViZERipKc4XzRHG7rZ6QscWqEAnpNNOgDoN9uHO7XTrMexGg453CEBegOaq6Juuq0poNEkhe4O1KYPFGDPGN1nfQwHGYpaSGMYdTHa63JRMrDoFMXU8pgeOOdA1YVtpA9COYdG@B81RLOP@fytuLkV8zy/zfllI4Gf338AGdM9WjBeXbrRK4jGK4w1WmCYzkoDvSI2Xj9GBn0YoE61PPqgSsTyx6CewD5Ig29zUCV8Xl6PXkJRS1RBcR9D23ivt@YbaFs0DuMOWCusy350WStoqgqjhlKXYJsAPc23jS0hNBCQsFU7ba22O6SChK/S6N@rUAd3aBtQ7N1iCT485X@zoqrP8H5w/8/Pji95ZqchZ7NsnQwpP5@TUZIkvwA "PHP ‚Äì Try It Online") - PCRE  
[Try it online!](https://tio.run/##bVJLbtswFNzrFK9uEZOWlIYJkIVkOUCPUHTRwjEEmaYlohJFkBTsJPC2B@gRe5C6j3TiTxEuCPJ9ZuYNybVOa873H6Xi7bASMF32vXWfjajF9rrRehbxpjJQ6vkCCvg6@rLZ/FzeDT@enr5/a@43DdmTbUzJQ/HI4k90T//PjxKY6KLUMcujE4lEDiOqbhYhXQt8SXivrINAnmVd5XhTGmGH1tnpIeVlTGZX0NEXI9xgFDgziHwXSeWgq6QiFF4iwKXnCN4KRTRN2aK4yWHAmrvb0kHvb76h9gfrVlmGtVLVGNSDy0P/hZRgBBiBYPlbzAZ9sGmq1451b4B42OcjbC1cK5Ug4cKlSg4MNH9T6ZdvUTfoa@V6SULBNS9REaE0AcUS0L3F9CGzlmpFxumY5kcAxTDraz4U59NkmfLBh3dwIQ71MTAKGZKfsMI7TzydEpvDba5YzBY5dKKzwhGbwHg79sLQC4tJb@6x/2iCLJR3eVoolkMcy/OJw9RrIM8UUJQnIeNHhSOhdSy/KBuUlbUSq@ASR1nnL1LWRmjClwmQ0/eACb3yslK5eDeOUSPoJcvhffrBwXQK0m8j@PPrN@545KfaXXTaX/8fzr7bs5Qx9pev26q2@7QNGssg8R8 "C++ (gcc) ‚Äì Try It Online") - Boost  
[Try it online!](https://tio.run/##LY5BTsQwDEX3PYUVIU1M2moMu5aIg5QuRpoUglKncoKYuQAH4IhcpIwFO/9vvydv1/qW@XGP65alQrmWVkL7XjKPIF6MMbu9OLTP/oXcHe63YqKho3mE6I/NkgUSRFawL/UceWgg@dSXLcVqTWewgbhACmwTPj0MkCaafZqOcwMKs8Jy4tdgI1erC2z/JprREd58KogDbKI9avY0wupVKqFfIp9PKVlpwVzMPaOe/P@TP2r/KbEGW6pYRneAn69vODiNK@JOHRH9Ag "Python 3 ‚Äì Try It Online") - Python  
[Try it online!](https://tio.run/##PY5BbsIwEEX3PcU0qhS7kFHM1rUQEmy7QOwCsmgZgiVriBwj0h6AA3DEXiR1QtXVaJ7@m/nh8vHVBzCwppq6BpmusFxsFhhof9DgTKnhenKewJuaYpvQEXxVqJ0x2ZYznbivSsRittNAfBgBto13UeRFLh8CeuI6noR8m6VAlewkPYQngOM5AINjGCDGs3VClRJxCP6v4yH3nAo1l9RjfOWM0tAExxF4msPP7Q75VGRd9soS2889i5Cm@6a/asM7a1fvS2t70U2kmJutmrzIvleFUuoX "Ruby ‚Äì Try It Online") - Ruby  
[Try it online!](https://tio.run/##RY9BasMwEEWvIsSApaoyUZcRIoGuewLXC@NOYoE8MrKCTYK3PUCP2Iu4TmjpanjD/4@ZIU6Yxg5DWCG5KuEZ53q/J5zEsVjFrKQ4uHejQK7F8Zm/xn7wAT@4tHB1O3uKCZu2ExCYJwaehkuWN2gcBD0OwWeuufUnAU3ZxgtlHTJ7uQeUg6ba1csmEECu8pTrx8YC6YB/bO6s1NboHaTyrclth6Mo5uIJSD7MV3mbks@ouzjmZbvK2H9mmuL2S/CEjAOx788vBgL6MiCdc/c7JF@W1WhjzA8 "PowerShell ‚Äì Try It Online") - .NET
```
(x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2;
               # return \2 as a match
```
[Try it online!](https://tio.run/##TY@7TsMwFEB/JUSoubdp0hohhga3E0OXDjACg9XeOhccx7LdB32sfACfyI@EVgKJ@ZzhnDe1UWHh2cUiOF6Sb1r7Th@dl5a2ySPph50D2MvJsN/BLkeYyheRX2PXH@6xjO1T9Gw1YBkMLwjuBsUtDpJMZ1gFOaq2NRsCMNKTWhq2BIhX0q6NwYOWpgzOcISsOOu8ArBSl4asjjVObo5HDnM1B5ZO@UAzG0E/j14R/wD9B3YipmJ8wRhr327Tmd0ow8vEK6tpnKS5qVath4rvJVWc53hoZLpLS0@OVATGslFxUYM/l/d67rwV4TIhKreOIXrgPEu@P7@SLIdm2vx2jkeI1enUiUII8QM "JavaScript (SpiderMonkey) ‚Äì Try It Online")
# Regex `üêò` (.NET), 15 bytes
```
((x+)(?=\2+$))*
```
[Try it online!](https://tio.run/##RY9BasMwEEWvIsSApbgyUZYxIoGuewLXC@FOYoEiCUnGJsbbHqBH7EVcp6F0@WY@b/4EP2JMPVq7QlRNxCtO7fHocGTnYmVsKjk7qfdDCZzv1uL8Ql/9LRiLH5TXcFf7@uIj6q5nYIlxBIwLQ@YzaAVWpGBNpoLW5sJAV50fXBY2k8MjUCrQzb5dNgEDpxrjcvs7qcEJi38sH1yWfH44bgpi9aZz12NixVTswPHn5s7nMZqMovcpL1szWf8zEc5vL1njkFBw5Pvzi8Bmq67RDyFtN6pOhzxETM@SnC7LskohpfwB "PowerShell ‚Äì Try It Online")
Returns its output as the capture count of group `\1`.
```
                   # tail = input number; no need to anchor, as all inputs return a result
(
    (x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2
)*                 # Loop the above as many times as possible, minimum zero, and push each
                   # match onto the \1 capture stack
```
# Regex (Perl / Java / PCRE2 v10.34 or later), 26 bytes
```
((?=(\2?+(x*))x(x\3)+$)x)*
```
Returns its output as the length of the match.
[Try it online!](https://tio.run/##RU7dSsMwFL7fU4QRlpy1XZeJN6ZZO5i3Xnm3jjBlg0DcalIhEuKlD@Aj@iL1rArefJzz8f11R2dvh5d3Qp0k0V6eD5bQUuKrqu3mcbNOk9PFcerVUlZrCZGYE34QO2fOPZm256lMpLHKd9b0nBUs929PvkeLzguRCzi@XkX1P7tEHu6oBnnN8th4cI2tVhAbuxN7hbjcyzQhZGw2fwQ1lRoFeGUZRPRyFligBtRHSV0JkfrZbNw1zsLNQv7OpGbByPfnF2EL3mSYVjQFIsiUktb3D1utB85rxdtVnfEwBwg8tDeQUQgwHwZRCCF@AA "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##bVLLbtswELznK7ZCA5O2w1jprYwatEULFGjaIj7aPtASZdOhKJWkYjmBr/2AfmJ/xF3K7COABQjk7g5nOcPdiAdxsSnuD6pqauthgzFTNRty@D/TeqVP5qxcyQ4rZ0271CqHXAvn4FYoA08Qc84Lj8tDrQqosEKm3iqzAmFXbrag4Ne23jr40OWy8arGk2cAH5WWUGZGbvstSVheF5JhPaH8XVuW0sriTopCWlj2sOdJ8udkDEtKeezrxp5v14GfEJctUYMoPisjCaUvMtNqTVVJHJPfW6EdSS6Hw2FC6dNz6JGBEH@S4AkZ/F8GJLhEhiXi7rkbZYO5GYTV8/0xt/8mvJfWgM3iDtVWTWjgKEc3lnWtpTDwmJXIKDlMc2EMSlemaT1kENTGHJnunJcVU4ZyiDp7GFsL90V2Hq/ZWwwQDdF4d@Q4ggwiosRYny1AYzmgmGu08iS5wEdAvAczwcon43EMLGuEdRIDomeTBR2DSU8WmZZm5dfXV3ADAQmvcUkXyJivhZ0tuqinj0y64PDWWrFzrFRak2486Aa9KQBlbYM2vEZmJhzMdWZSXEYjFHgrfL5Ghypks6w6RqSfXIMD/h7JjxPDtlY0JLbI62b3tbwTZiWx02RsKA1KSyAVtjcFehfe9pFGk2t0bGuVlyQ8KuWPmbdteJ9/5QY99CVJzgv49eMnnBcJOjOGiq1s3TZkQqMfSM334TsLE3cg5CbD/8386oaSbkhpR7r5Kzp6STs6PISROqQXaZr@Bg "Java (JDK) ‚Äì Try It Online") - Java  
[Attempt This Online!](https://ato.pxeger.com/run?1=fVPBbtNAED1wy1dMrVW929hpXC4VrhUJ0aIgaFEIpyRaOfY6XrpZW7ubyqjtlQ_gyqUS4if4FI58CWOHFIEiDl7P7Lx5Mztv98vXuqwffjy5OBuhAcRAAt6xBwOojVhxI2qVZoL6x4OjEedlqhzPqnUtlTBzOmfxfHJs_QB8_Arc5CvRArQT2lnK-cX49TnnLICIISUSxz2pJbfCUa_OjBgs0-zaGVy4kmvpvAC8MPJY_DfKiGxjrKz0f1EftpEhBnpFZSiRyTAmKimwKUvfTV-ML1nMbkEWlKiZdUYJjRYLo0WSeHPtMQTbzRIjuB0MgzBibb5oalXlgnqhFyA8xvys2mjX5p6dYNIMCXAdLuIeQFdZ__aJPku6OFr9PoNbBAA2APSAkuukm_E6dVlJiQmwbjtwkTrqN35ANAvImjEGRGyRKrWOC2OwAosfmcg13N0h5iBJ3k7OX_LLK34-mVxNsFp7UslEVlbt8WLAiUQxtD4QPfDg56fP4A12k1hjxyy-_9MiMh8e7mXuKPxn4A9mKL0_RsGNThV0zeHG852s0AkGoinTjXUix9hkJ-ae2JtU4fzWIof304vwFLIyRRYktwHUlbVyqT6C1Fll8Eo4tAXaeZc6LQVURYHXAXKZg64cdDBbVzoHV4FDwFKspNZSrxAKKdykSj6WQh6sIbVDslfjKVi3r__FjIhO5_ve_T8PAkX5tnFFePqd0lFC5yejPm2OGGtoM3_K-oQ17GgLeNj9ojCKoq3zCw "PHP - Attempt This Online") - PCRE2 v10.40+
We can't just do a direct port of the .NET version, because we need to subtract at least 1 from tail on each iteration (as a regex loop terminates after a zero-width match), and with most inputs, the iteration count exceeds the cumulative result of subtracting the largest divisor before the last iteration has finished. So instead, we let `\2` be the sum of the subtracted divisors minus the iteration count:
```
                    # tail = input number; no need to anchor, as all inputs return a result
(
    (?=
        (\2?+(x*))  # \3 = {conjectured largest proper divisor of tail-\2} - 1;
                    # \2 = {\2, or 0 if \2 is unset} + \3; tail -= \2; note that the
                    # subtraction of 1 from this divisor compensates for the "tail -= 1"
                    # on each iteration (below)
        x(x\3)+$    # assert tail - 1 is divisible by \3 + 1
    )
    x               # head += 1; tail -=1
)*                  # Loop the above as many times as possible, minimum zero
```
(The PCRE version requirement is because PCRE2 v10.33 and earlier automatically makes any group containing a nested backreference atomic, thus `\3` always captures the entire remaining tail, making the regex always return 0.)
# Regex (.NET), 28 bytes
```
(?=((x+)(?=\2+$))*)(?<-1>x)*
```
[Try it online!](https://tio.run/##RY/BboMwDEB/JUKWSMqCmh7LslXaeV/AOCDmQqTUQSEIVMR1H7BP3I@wsGnayX629Wz3bkI/dGjtBl6XHlucq/OZcOKXdOPPmvM5EzG@nTIQ4hDTR6meZnHY0stD8uJuvbH4nogC7vpYXJ3Huuk4WGaIgaF@DGKBWoOVQ29NSGRSmCuHOm/cSEHawE77QKahLo/VGgUcSJeGQvVTKYCkxT9WO2eZWHbHTYPPX@vQdDjwdE4PQOK3cxfL5E1A2bkhrPEyVfwzk@Tif9YQsgSIfX18Moi2vPVu7Ie4M7dIbehEsq7rpqRS6hs "PowerShell ‚Äì Try It Online")
A simple port of the 15 byte .NET version, that returns its output as the length of the match instead.
## Regex (Perl / Java / PCRE2 v10.34 or later / .NET), ~~29~~ bytes
Obsoleted by the 29 byte regex below, which supports a superset of regex engines.
# Regex (Perl / Java / PCRE / Python[`regex`](https://github.com/mrabarnett/mrab-regex) / Ruby / .NET), ~~33~~ 29 bytes
```
((?=.*(?=\3$|^)(x+)(\2+$))x)*
```
[Try it online!](https://tio.run/##RU7LSgMxFN33K0IJTW7nmYobM2mnULeu3HVqqNJCILZjMsJIjEs/wE/0R8bbUXBzuPdwXu3B2evh@Y1QJ0mw56e9JbSQ@Kpqs75fL@PkeHacelXKaikhEHPED0LrzKkj0@Y0lZHUVvnWmo6zjKX@9dF3aNFpJlIBh5eLaPXPlsjDDdUgL1keG/euttUCQm23YqcQy52ME0LGZvNHUFOpUYBXkkBAL2c966kB9VFQV0CgfjYbd42zcLOQvzOpyRn5/vwiLOd1gmlZnSGCjDFqfXu30XrgfKXyOUJzRd8fgPcJ8GaRUIAe5sMgMiHEDw "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##bVLLbtswELznK7ZCApN@MFZ6KyMEbdECBZq2SI6OC9ASZdOhKJWkYsWur/2AfmJ/xF3K7CNAdBC5u8NZznDX4kFM1sX9QVVNbT2sMWaqZkMO/2dar/SzOSuXssPKSdMutMoh18I5uBbKwA5iznnhcXmoVQEVVsitt8osQdilm80p@JWtNw7edblsvKrx5AnAe6UllJmRm35LEpbXhWRYTyh/05altLK4kaKQFhY97GmS/DkZw5JSHvu6seebVeAnxGUL1CCKj8pIQumLzLRaU1USx@S3VmhHkvPhcJhQunsKPTIQ4p8l2CGD/8uABOfIsEDcPXejbHBnBmH1fH/M7b8I76U1YLO4Q7VVExo4ytGNRV1rKQxssxIZJYfbXBiD0pVpWg8ZBLUxR24fnZcVU4ZyiDp7GFsJ90l2Hq/ZWwwQDdF4d@Q4ggwiosRYn81BYzmgmGu08iSZ4CMg3oOZYuWD8TgGljXCOokB0bPpnI7BpM8WmZZm6VeXF3AFAQmvcEnnyJivhJ3Nu6inj0w65/DaWvHoWKm0Jt140A16UwDK2gZteI3MTDmYy8ykuIxGKPBa@HyFDlXIZll1jEg/uQYH/C2SHyeGbaxoSGyR183j5/JGmKXETtOxoTQoLYFU2N4U6F142y2NJtfo2MYqL0l4VMq3mbdteJ9/5QY99CVJzgr49eMnnBUJOjOGii1t3TZkSqMfSM334TsJE3cg5CpjQ/zdvTz9/pWSbkTJ3cXolNKODg9hpA7pJE3T3w "Java (JDK) ‚Äì Try It Online") - Java  
**[Try it online!](https://tio.run/##hVTbbtpAEH3nK6Y0CbvYRDhIVWXjRGmaqg80qVAitQJqUbOGVc3aWi@FJPDaD@gn9kNKZ3dx4lykWsjay8w5Z86MifO8NY3j7Wsu4nQxYdDNY8kOZ8e1eDaWEOWDEYTQr79bLn987yy@3tx8uZq9Wc7IlpCT8LCJr2Fnb/2NkpVDyfDI2aN0RZtb@jSh7kIzD6Pc8YLaA1mhJjzTbNUjycX08RnP8JSN58/jjmtcKMhxqSImZSZJnIlCgVHfnLOiGE8ZvUMe348xALpd2J3qpTlnYpIGIJlaSAFesDGQ8zEXhMJdDfDJB8iWMkFy2vJGYTuABcZ0jiIFmd7phCkuTLDBtOrwIl@oALSn0JQsgKo6lJMrabMlKxapsmtdR5IUTLmQLRTSTtXM3mQ/WawyOeiMLBWihgY8irN5zlNGchc@n/XPo/eXV6e9Hqzt7vrqw1sXDiyhXZQMbWqheALklWS09CExniYEq8FoF@oayEiTMEYlJh32Jz7sF0OB3a1gWp4dcIIJRIu/1U4Zc6ZMpVwwYrvChWt9ogHGeKXnRhSmiTbWOFYZJyboMI7QW0KpC8JzIc8KvLY3CRcT0mg1dsT6EZ42CGNehdW@@L7Qhycv4IJj4h1AIT6SP2DZpmk6wZZ2NxCe440CnKg5Fk4KFxqrhhaGpRR4OQor@fdG8FDomemGwgvAcXi1YttVPQtlZ9mKxUQyFy6uez0XkINj18xvNw4udColl83coRyH0Ib1ugRFH8xEnPf7l/3o4vLT6dXZx6cCSohbCuiMrpQ0hqJh@xM8C7VtxFHVXxTXrzr8@fUb37gsR9YbBS9y7HR1UeXBwX9UPiKq@3Cup7H@GHfzspWVPtiITc3Msm9nVDKGSuj9v8Duc6xttl7L87y/cZKOp8W2leqW/AM "C++ (gcc) ‚Äì Try It Online") - PCRE1  
[Try it online!](https://tio.run/##fVPBjtowEL3zFbORtbEhBLK9VA0RUlW2YtXuVpSegFohMcTFOJFtKqqFaz@gn9gfoZNs2aoV6iGj8cybN@N5TlVUp8GwKiogBhLweh6EUBmx5kZUKs0E9Xthe8h5kSrHs3JbSSXMnM5ZPJ/0rB@Aj98Kg3wtaoB2QjtLOb8dvxtxzgKIGFIicdySWnIrHPWqzIhwmWYbZ9BwJbfSeQF43chj8d8oI7KdsbLU/0V9ecr0MdFalYYSmfRjopIVDmXpx@mb8T2L2SPIFSVqZp1RQqPHutEiSby59hiC7W6JGQwH/aAbsbpe7CtV5oJ6XS9AeIz1WbnTrq4d3GDRDAnQ9hdxC6DprH@fiR4kTR69TofBIwIABwB6RckmaXa8TV1WUGIC7FsvXKSO@ns/IJoFZMsYAyKekCq1jgtjsAOLn5nIBg4HxFwlyYfJ6C2/f@CjyeRhgt3qm0omsqKsrxcDbiSKoT4D0aEHP7//AC88b2KLE7P4@GdEZL6@vsjcUPivwA9nKL0/RsGNThU0w2Hg9VlWaAQDsS/SnXUix9zkLOaF3PtU4f62IodP09vuS8iKFFmQ3AZQldbKpfoGUmelwSfh0Bfo503ptBBQrlb4HCCXOejSQQOzValzcCU4BCzFWmot9RqhkMLXVMnnVsiDPaR2SHY3noJ1l@ZfzIhodD62jv/8ECjKidJhErbRzF@Qw2dG9x1G5zcdwtietU@nqBtF0S8 "PHP ‚Äì Try It Online") - PCRE2 v10.33**  
[Attempt This Online!](https://ato.pxeger.com/run?1=fVPBbtNAED1wy1dMrVW9m9hOXC4VrlUJ0aIgaFEIpySsHHsdL92srd0NCmp75QO4cqmE-Ax-hCNfwtghRaCKg8ezO2_ezM7b_fK1qZq7H4_OT07RAWIgBW_oQQSNEStuRKOyXFB_GPVPOa8y5XherxuphJnTOUvmk6H1A_DxK3GTr0QL0E5oZynn5-OXZ5yzAGKGlEic9KSW3ApHvSY3Ilpm-ZUzaLiSa-m8ALww9ljyN8qIfGOsrPV_Ue93kREGemVtKJHpKCEqLbEpS99Mn40vWMKuQZaUqJl1RgmNHgvjRZp6c-0xBNvNEiO4HYyCMGZtvtg2qi4E9UIvQHiC-Xm90a7NPTnCpBkSoB0tkh5AV1n_XhN9knZx9AYDBtcIAGwA6AElV2k343Xm8ooSE2DdduAic9Tf-gHRLCBrxhgQsUOqzDoujMEKLLlnIldwc4OYgzR9PTl7zi8u-dlkcjnBau1JJRN5VbfHSwAnEifQroHoyIOfnz6DF-0nscaOWXL7p0VkPjx8kLmj8J-AH81Qen-MghudKeiaw42ne1mhEwzEtso21okCY5O9mA_EXmUK57cWBbydnofHkFcZsiC5DaCprZVL9RGkzmuDV8KhL9AvutRpJaAuS7wOUMgCdO2gg9mm1gW4GhwClmIltZZ6hVDI4EOm5H0p5MEaUjskezGegnUP9b-YEdHpfNu7_edBoCjfNq4Mj79TeppGfTTzx-TmHaPbAaPzowFhbMv6O8zd_heHcRzvFr8A "PHP - Attempt This Online") - PCRE2 v10.40+  
**[Try it online!](https://tio.run/##PY5NasMwEIX3PsUgApnxH1GysytyEMcF0yqJijw2kkId6LoH6BF7EVdKaTfDm5/3zZvv4TrxYTXjPLkA/u5Lpy96Kd/8xC045YQQK@JR1Xksp8Pm45lwKQhP@2JDtFC@xotONpXsWzBql50nBxYMJ1jtw6vhJgOrbO1nawKKSlAG5gxWM1p62jdgO9kr2@36DJKZk9kNfNFoOGBaUPmrZE@FpMiDUT1y1l4P7uWKrgSxiJwjOrHHdJKEaWB2yUvtY6Jk@5druoX63Zmg0QeHTMUWvj@/YFukdoxpB0aKH6t/HXPQKisp5Q8 "Python 3 ‚Äì Try It Online") - Python `import regex`  
[Try it online!](https://tio.run/##PY7BasMwEETv@YqtMbXWiRfLPbqiBNJrDiU3OxUtURyBUIyiEBdCj/2AfmJ@xJWdJpeBeczsjjt@fvUOBLypRnUtWXWCxXw1J6c@NiVokZdw2mmjwIhG@UNAWzBVxtdCRLWNysBNlRNlxboEZTcjoENrtGdJluC1QEbZxu8YPhchUIV2KF0LE4Dt3oEFbWGA5PdSM54j0RC82/EQi7ootQjiG9wI9MOwsD0Oy8bvWvDgnbYe7CyBy88vJLP48T7gP3aTiZSvy4WUPWMvgtIg9VN8fkfWTZHVxTRG7DDte55xzv8A "Ruby ‚Äì Try It Online") - Ruby**  
[Try it online!](https://tio.run/##RY9RaoQwEIavEsKAiTay2b6thC70uSdwLYjNaiA7kRhR1vraA/SIvYiNLaUvA9/8wzczvZu0Hzpt7QZelV63eq5OJ9QTOycbY08qT2O5PML7K2dzxtnlmAHnM0@35PxAn92tN1a/UV7AXR2Kq/O6bjoGlhgkYLAfA1@gVmDF0FsTqKCFuTKo88aNGIQN5LgPZArq8lCtUcAAVWkwVD@dAlBY/cdy5yzjy@64KfD5Sx2aTg8smZMUkP8md75M3gQtOjeENV4mi38mAl180BrUhAKSr49PAtGWt96N/RB35lZjGzpO13XdpJBSfgM "PowerShell ‚Äì Try It Online") - .NET
For regex engines that lack nested backreferences but support forward-declared backreferences, we switch to a different approach. In this version, each iteration, while inside a lookahead, stores the new value of tail in the capture group `\3`, so that the next iteration can then recall that value rather directly. Since this directly sets `\3` instead of building it up incrementally, there's no need to emulate a nested backreference.
```
                     # tail = N = input number;
                     # no need to anchor, as all inputs return a result
(
    (?=
        .*(?=\3$|^)  # tail = \3, or N if \3 is unset
        (x+)(\2+$)   # \2 = largest proper divisor of tail; \3 = tail - \2
    )
    x                # Increment the return value
)*                   # Loop the above as many times as possible, minimum zero
```
# Regex (Perl / PCRE / Python[`regex`](https://github.com/mrabarnett/mrab-regex)), 63 bytes
```
(?=(xx+?)\1*(?=\1$)((?R)))(?=(x+)\3*(?=\3$)((?R)))\2\4|x\B(?R)|
```
This implements the recursive definition of the function:\$a(1) = 0\$  
\$a(p) = 1 + a(p-1)\$ if \$p\$ is prime  
\$a(nm) = a(n) + a(m)\$ if \$m,n > 1\$
[Try it online!](https://tio.run/##RY5BTsMwEEX3PYVVWbWHJG3cwgbHTYrKtgvEDldWQa1kybTBDlKQa5YcgCNykeAEBJvR/Dczf369t@aqe35D2HLkzelpZxCe8ShFsV7dr5ZhdDhZip3IebHk4JE@RAW@tvrYoLE8jnlAlRGuNrqhJCOpe310TTxRacZSBvuXfqn8p3nkcI0V8N7LxY87W5liDr4yD2wrYs23PIwQGj7rX4B1IYaF2CUJ@HhLSUtarEG8z7CdgcduMhlyDbFiZsZ/YmI9Jejr4xORKa2S6JZVWazAQwhK3W7WSnW0FLRtkxIku4i9ZBgoLe8AYJgkIBcDX/xxOZeX51be9OrcdSxjjH0D "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##hVTbbtpAEH3nK6a0CbvYRGyoqsrGQUmaqg80qRCRWmFkUbMGq2ZtrU0hCbz2A/qJ/ZDS2V2cOBepFrJmZ2fOnDkzJsyy1iwMd69jESbLKYduFkp@ND@phfOJhCAbjcGDQf1stfrxvbP8dnPzdTh/t5qTHel5ZL22etRnTbR99oYS0htQSvWNRf2O9nfu/f6x/3az9s/UabOjTyHrNjQzL8gs5tYe6OTFNE4Vn6pLxmL22Ben6OWTxfO4k1osCsjQLAIuZSpJmIq8AN1fc8HzfDLj9A7rOE6IAdDtwt6rTO3nYpq4IHmxlAKYu9WQi0ksCIW7GuCTjbBawgXJaIuNvbYLS4zpHAcFpOqkEmZo6GCNadjhRbYsXFCqQ1NyF6rskE5WSJMteb5MCmOrPqIo54UN6bLAsrNibm7SnzwsUjnqjE0pRPU0eBCmiyxOOMls@HI@uAg@XA1P@33YmNP18ON7Gw5NQWOUFdrUQMURkFeS01KHSGsaEewGo22oKyBNTcIEmeh0OJg6cJD7AqdbwTR19sARJhBF/lYppcWZ8SKJBSdmKrGwjU7UxRhWaq5JYZpoY4@TIo2JDjoKA9SWUGqDYDZkaY7X5iaKxZQ0Wo19YfUIpgTCmFdedS6OI5Sz9wIuWDreAiTiYPEHLDM0VU7wlTmNBLPY2MWNWmDjJLehsW4oYthKjpdjr5J/L0TsCbUzXU8wFywrrnZspqp2oZwsX/OQSG7D5XW/bwPWiHFq@rdfBxs6lZbLYe5RTjxow2ZTgqIOeiMuBoOrQXB59fl0eP7pKYES4pYCKqM6JQ1fNMx83GehZoy4quqLitWrDn9@/cY3muXKsrH7Yo09ry6yPDz8D8tHheoOXKhtrD/G3b4sZWUOJmJb07vsmB2VnCMTev8vsP8ca9sdazHG/oZRMpnlu1aiRvIP "C++ (gcc) ‚Äì Try It Online") - PCRE1  
[Try it online!](https://tio.run/##fVPdbtowFL7nKU4jq7FLoKTdxbQQIVWjE9PWThm7IsgKiSEexolsUzGV3u4B9oh7EXaSjk6b0C5inZ/vfOf4fE5d1ofhqC5rIAZi8C496ENtxIobUassF9S/7F@MOC8z5XhebWqphElpyqI0ubR@AD5@SwzylWgA2gntLOX8dvJhzDkLIGRIicRRR2rJrXDUq3Mj@ossXzuDB1dyI50XgNcLPRb9jTIi3xorK/1f1NfnzAATnWVlKJHxICIqXuJQln6evp3csYg9glxSombWGSU0WqwXzuPYS7XHEGy3C8xgOBgEvZA19WJXq6oQ1Ot5AcIjrM@rrXZN7fAKi2ZIgOdgHnUA2s76t0/0MG7zaHW7DB4RADgA0DNK1nG7403m8pISE2DfZuEic9Tf@QHRLCAbxhgQ8YxUmXVcGIMdWPTCRNaw3yPmLI4/JeN3/O6ej5PkPsFuzU0lE3lZNdeLADcSRtD4QHTfg5/ff4DXP25igxOz6OnPiMh8fn6SuaXw34Dfn6H0/gQFNzpT0A6HgZujrNAKBmJXZlvrRIG55CjmidzHTOH@NqKAL9Pb3mvIywxZkNwGUFfWyoX6BlLnlcEn4dAWaBdt6bQUUC2X@BygkAXoykELs3WlC3AVOAQsxEpqLfUKoZDBQ6bkSyvkwR5SOyR7P5mCdafmn8@IaHV@6jz980OgKAc6iulu1x2xNLxAOw0Jo3SUoIptpsvS6zZ@/RJPr9JX@11603j7wyHshWH4Cw "PHP ‚Äì Try It Online") - PCRE2 v10.33  
```
                # tail = input number; no need to anchor, as all inputs return a result
    (?=
        (xx+?)\1*(?=\1$)  # Assert tail isn't prime;
                          # tail = \1 = smallest prime factor of tail
        ((?R))            # \2 = recursive result of f(tail)
    )
    (?=
        (x+)\3*(?=\3$)    # tail = \3 = largest proper divisor of tail
        ((?R))            # \4 = recursive result of f(tail)
    )
    \2\4                  # return \2 + \4 as the match
|       # or if tail is prime:
    x                     # tail -= 1; return result += 1
    \B                    # Assert tail > 0
    (?R)                  # return 1 + recursive result of f(tail)
|       # or if tail == 1:
                          # return 0 at the match
```
Note that `(?0)` could have been used as a synonym for `(?R)`.
# Regex (Perl / PCRE / Boost / Python[`regex`](https://github.com/mrabarnett/mrab-regex)), 65 bytes
```
((?=(xx+?)\2*(?=\2$)((?1)))(?=(x+)\4*(?=\4$)((?1)))\3\5|x\B(?1)|)
```
The intent of the 63 byte version was to create a version that works under Boost, but as it turned out Boost has a bug (which I've [reported](https://github.com/boostorg/regex/issues/177)) in which it ignores top-level alternatives in a top-level recursive call (i.e. `(?R)`), trying only the first top-level alternative. The workaround is to nest the entire regex in a capture group, so that Boost sees the other alternatives. Either `(?R)` or `(?1)` would work, but the latter is used for slightly better efficiency.
[Try it online!](https://tio.run/##RY5BTsMwEEX3PYVVWY2HJE0c2g2OmxSVbVfscBUV1EqWTBviIAW5YckBOCIXCRODYDOa/2bmz68PjVkOz2@ENoI4c37aG0ITgVLmm/X9etVPjueGUStTka8EOKKPqMDVjT61ZKpOU9GT0khbG92yIA4i@/poWzypophHHA4v41LxT1PkcEMrEKOXxY/7pjR5Bq40D3wnsaY70U8I8Z/1L6A6l34BuzAEh7cs6IKOapDvCW0ScNTOZj6Xj4WZufiJSfU8IF8fnySYszJEt7iMsYLo@76q7rabqhoYKyTrurAAlV1hrzIKyDgA@EkIauH54o@ra7W8dOp2VBcYBh5zzr8B "Perl 5 ‚Äì Try It Online") - Perl  
[Try it online!](https://tio.run/##fVPdbtMwFL7vU5xF1mKv6U/GkBBpVGmiQ0WwoVKumslKE7cxdZ3IdlHQ2lsegEfkRcpJRodAExexzs93vnN8PqcqquNoXBUVEAMxeAMP@lAZseZGVCrNBPUH/Ysx50WqHM/KbSWVMAlNWJTMBtYPwMdvhUG@Fg1AO6GdpZzfTN9POGcBhAwpkTjqSC25FY56VWZEf5lmG2fw4EpupfMC8Hqhx6K/UUZkO2Nlqf@L@vKYGWKisyoNJTIeRkTFKxzK0k/zN9NbFrEHkCtK1MI6o4RGi/XC@zj2Eu0xBNvdEjMYDoZBL2RNvagrVeaCej0vQHiE9Vm5066pHV1i0QIJ8BzeRx2AtrP@7RM9its8Wt0ugwcEAA4A9IySTdzueJu6rKDEBNi3WbhIHfVrPyCaBWTLGAMiHpEqtY4LY7ADi56YyAb2e8ScxfHH2eQtv73jk9nsbobdmptKJrKibK4XAW4kjKDxgei@Bz@//wCvf9rEFidm0eHPiMh8fv4sc0vhvwa/v0Dp/SkKbnSqoB0OA9cnWaEVDERdpDvrRI652UnMZ3IfUoX724ocPs9veq8gK1JkQXIbQFVaK5fqG0idlQafhENboJ23pfNCQLla4XOAXOagSwctzFalzsGV4BCwFGuptdRrhEIKX1Mln1ohD/aQ2iHZu@kcrHtu/vsFEa3Oh87hnx8CRTlSOo5pXXfHLLm8QDu5JAxjIcrYZrosuWrjV0/x5EXycl8n1423Z8dj2AvD8Bc "PHP ‚Äì Try It Online") - PCRE2  
**[Try it online!](https://tio.run/##bVLNcpswEL77KbZup5YMOJGd9gAmnskjdHpox3gYIsugKRYaEIOTJtc8QB@xDxJ3JWripOWg2d9v9/sWrnWQc358LxUv262A5W1VNeaiFrk4zAqtr0e8yGpI9XoDMXwZ33Tdj9tF@/3u7tvX4nNXkCMhq5gcDt6KJvMp2sn8A8UYo5S6jEeTKxe/GuLJIvn0cEhurPdAj/Qt6NiHqY5T7bFo9LKZxMVqke2vR1IZ2GdSEQo/R4CfXmOqFIpoGrBNfBlBizWLeWqgsp5tyK3RmG0YYq1UOQZ1ayLXzyvVGHDUw9Bxh1ogWHSKNfvM8AK6IvvbsatqIBb2foDNhSmlEsQ5XCq/n0Cj05b2sy3qEqXMTCWJK5jxFDcilPqgmA@6ajDdZ3ZSbckkmNBoAFAMs7bmXXzOJgyVDa7@gwueq/eAUQhx@AuWO@3UjlOi6721Yh7bRLAX@0YY0vgwOUzsYqhFg0kr7tA/iCBjZVVexopF4HnynLFjvQNyrm7aiKzmBSFnDOhHix/Ije9k9vEC9C3OCeueAhK0C5NJolAePAOL/intL1G1BpZLkPYZw@@nX/iiaYfM8J/JTUHo697H0Wurf2th2loB8n88soAx9sx3ZZY3x6B03FJH7Q8 "C++ (gcc) ‚Äì Try It Online") - Boost**  
[Try it online!](https://tio.run/##PU9LboMwEN1zipFVKZ4YUEzSDdSK1GtgFqh1EkfGINtViZR1D9Aj9iLUpmp2b97M@8x0C5fR7hc9TKML4G8@d@qs5vzqR9uAE44QslB6FHSe2RFltY1YVk8YOY6I64ahPKz84cHLvXy@z/I1TXdcokvL64J3DWixy06jAwPapsDSh3dt6wyMMKWfjA6UFAQz0CcwylKDL1UNpuWdMO2uyyCJbRK73p4V1TbQtMD8D/EOGcfoB4NYfym96t3bhbocyEy2Nlon7yGdJKBrmFzSYrMygjf/vcaPUH46HRT1wVGLbAM/X9@wYWkcYtveUoyJxQPHHrjwgnP@Cw "Python 3 ‚Äì Try It Online") - Python `import regex`
# Regex (Ruby), ~~76~~ 71 bytes
```
(?=(xx+?)\1*(?=\1$)(\g<0>))(?=(x+)\3*(?=\3$)(\g<0>))\k<2+0>\4|x\B\g<0>|
```
[Try it online!](https://tio.run/##RY5BTsMwEEX3PcUQVcRuGstO2SVuVVS2LBC7uIpAdVMLy41cVzVSxZIDcEQuEhwXymY08/7/9rfH1/feAocn2UrfESNPsFo@L4mVL5sSFKclnHZKS9C8le4Q0BZ0nbM154kwSRm4rikhebEuQZpNBOTQaeVQmqf4EiBamtbtEK6KYKhDOoQugRHAdm/BgDIwQOL2jUKMYkIG4/WMD6HEJxODgX@AjUDdDA2749As/q44C7dVxoGZpvD9@QXpdHx7LfBr@xujpnl4XDVNjxYceZ8tsGCTsAs2xki0FZ1jHKUMi1kUZv@CeKuKjM7F3dmL@8jOfc9yxtgP "Ruby ‚Äì Try It Online")
This is a port to Ruby's style of recursion; `(?R)` is replaced with `\g<0>`. Also, the backreference `\2` needs to be replaced with `\k<2+0>` to get its value at the current level of recursion, rather than its global value which may have been overwritten at deeper levels of recursion.
[Answer]
## Mathematica, 36 bytes
```
f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1
```
An unnamed function takes the same bytes:
```
If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&
```
This is a very straightforward implementation of the definition as a recursive function.
[Answer]
## PowerShell v2+, 81 bytes
```
param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j
```
Brutest of brute force.
Takes input `$a`, enters a `for` loop until `$a` is less than or equal to `1`. Each loop we go through another `for` loop that counts down from `$a` until we find a divisor (`!($a%$i`). At worst, we'll find `$i=1` as a divisor. When we do, increment our counter `$j`, subtract our divisor `$a-=$i` and set `$i=0` to break out of the inner loop. Eventually, we'll reach a condition where the outer loop is false (i.e., `$a` has reached `1`), so output `$j` and exit.
**Caution**: This will take a *long* time on larger numbers, especially primes. Input of 100,000,000 takes ~35 seconds on my Core i5 laptop. *Edit* -- just tested with `[int]::MaxValue` (2^32-1), and it took ~27 minutes. Not *too* bad, I suppose.
[Answer]
# Octave, ~~59~~ ~~58~~ 55 bytes
```
function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end
```
> 
> Updated thanks to Stewie Griffin, saving 1 byte
> 
> 
> Further update, saving three more bytes by using result of factorization in while-check.
> 
> 
> 
Sample runs:
```
octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9
```
[Answer]
# Haskell, 59 bytes
```
f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))
```
Usage:
```
Prelude> f 30
Prelude> 6
```
It may be a little inefficient for big numbers because of generating the list.
[Answer]
# Python 3, ~~75, 70~~, 67 bytes.
```
g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]
```
This is a pretty straight forward recursive solution. It takes a VERY long time for the high number test cases.
[Answer]
# Matlab, 58 bytes
```
function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `s`, 6 bytes
```
‚ÅΩ‚àÜ·π´‚Üîv‚Ä†
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJzIiwiIiwi4oG94oiG4bmr4oaUduKAoCIsIiIsIjE1NzA0Nzc4MTE2NTcyMzcyMTcwMzg0MTE1MjA2MjAzNzA0NTc3NDE0MzE5MTcxMTU4NDQxMTkzNDA4NjA4MzYzNjcwNzY3OTUzNTA4MDI0MDE2NzY4OTMzNjg5Njk5MTIxMTIzMjk5Nzk1OTY1MzM2MTgyMTUyNzMwNjk2MTg1ODYwOTU2NzYyMjI4OTg4ODgwNjUwNTU2MjU4Mzk4MzkyOTA5NTQzMjE1NzMzMDI3NTMyOTgxNjMwNzc2MTM3ODUzODgxMTE2ODM4MDQyMTc2NzYzMTA5NDU3MDAwMDY0MTM2ODAxNTU4MDE3MjY3NDM0MTU5MTM2NzM3ODUwMTgxODkzOTcyMDEwNzk5NTYxNDAxNzE4MjY4OTIyMDk0NjE5NDg4NDczNDEyNTI1NDM5NTMxOTc0NDA1MjA0MjA1ODQxOTY5NDMwNTE1MDUyMjc4Nzc2MDQ1ODY2NDk0OTUyMzc3ODk2MTEwOTI0MTc1MDk4NzYwOTk5MzU3OTYxNDY1ODQ5OTExOTg3Mzc4MjkwMTg2MTY4OTI1Njg2MzgzODEzNjY5MjExMDE2OTE3NDkyNDkzMTU1OTE0NDAxNjQxNDE1OTM1OTY2Mjc1MjAyMjY1NDM5OTY3MjgzNDYxMzQ1NTMzMDA4NzkyMDM0MjU4NTUzOTY1OTQzMjk4NDU3NiJd)
Port of Jelly.
```
‚ÅΩ‚àÜ·π´‚Üîv‚Ä†
‚ÅΩ  ‚Üî    # Repeatedly apply until the result does not change, collecting intermediate results:
 ‚àÜ·π´     #  Euler's totient
    v‚Ä†  # For each, get the number of distinct prime factors
        # s flag sums
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `l`, ~~6~~ 5 bytes
```
‚â¨K¬Ø√∑·∫ã
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJBbCIsIiIsIuKJrEvCr8O34bqLIiwiIiwiMVxuMlxuM1xuNFxuNVxuNlxuN1xuOFxuOVxuMTBcbjExXG4xMlxuMTNcbjE0XG4xNVxuMTZcbjE3XG4xOFxuMTlcbjIwXG4yMVxuMjJcbjIzXG4yNFxuMjVcbjI2XG4yN1xuMjhcbjI5XG4zMFxuMzFcbjMyXG4zM1xuMzRcbjM1XG4zNlxuMTAwXG4yMDAiXQ==)
This is the same as the 6 byte answer below except the length is taken by the `l` flag rather than a `L` element.
# [Vyxal](https://github.com/Vyxal/Vyxal), ~~7~~ 6 bytes
```
‚â¨K¬Ø√∑·∫ãL
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCLJvihu4oK0YCA9PiBg4oK0bs67Iiwi4omsS8Kvw7fhuotMIiwiO+KAoCwpIiwiMTExIl0=)
```
‚â¨    # 3-element lambda:
  K  # Push a list of the divisors, from 1 to the number itself in increasing order
  ¬Ø  # Deltas - returns a list of the consecutive differences in the list.
     # The resulting list has a length of 1 less than the one fed to it.
  √∑  # Unwrap the list onto the stack. For a non-empty list, this is effectively
     # equivalent to t (Tail - get the last item). But for an empty list, the
     # result is effectively whatever was already on the stack, i.e. the the
     # number whose list of divisors was taken, i.e., 1, the only one that yields
     # an empty deltas list. This makes 1, instead of 0, the fixed point.
·∫ã    # Repeat the lambda on the number at the top of the stack (which is initially
     # the input) until the result no longer changes, returning a list of the
     # results. The last result will be 1, our fixed point.
L    # Length
```
This is very slow for most numbers of more than 60 decimal digits or so, since it has to generate a full list of divisors (even if it only uses the largest two). Prime factorization is still fast enough at that level, but unless the number has only one distinct prime factor, the list of divisors will be orders of magnitude longer.
[Answer]
## [Japt](https://github.com/ETHproductions/japt), 12 bytes
```
@!(U¬µUk √Ö√ó}a
```
[Test it online!](http://ethproductions.github.io/japt/?v=1.4.3&code=QFW1VWsgsqTXIKUxfWHE&input=MzA=)
### How it works
```
@   !(U¬µ Uk √Ö  √ó   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression
```
This technique was inspired by the [05AB1E answer](https://codegolf.stackexchange.com/a/79648/42545). A previous version used `¬≤¬§` (push a 2, slice off the first two items) in place of `√Ö` because it's one byte shorter than `s1¬†` (note trailing space); I only realized after the fact that because this appends a 2 to the *end* of the array and slices from the *beginning*, it in fact fails on any odd composite number, though it works on all given test cases.
[Answer]
# ><>, 32 bytes
```
<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln
```
Expects the input number, `n`, on the stack.
This program builds the complete sequence on the stack. As the only number that can lead to `1` is `2`, building the sequence stops when `2` is reached. This also causes the size of the stack to equal the number of steps, rather than the number of steps +1.
[Answer]
# Ruby, 43 bytes
```
f=->x{x<2?0:1+f[(1..x).find{|i|x%(x-i)<1}]}
```
Find the smallest number `i` such that `x` divides `x-i` and recurse until we reach `1`.
[Answer]
# Haskell, 67 bytes
Here's the code:
```
a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)
```
And here's one reason why Haskell is awesome:
```
f = (2&)
(-->) :: Eq a => a -> a -> Bool
(-->) = (==)
h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]
```
Yes, in Haskell you can define `-->` to be equivalent to `==`.
[Answer]
# Matlab, 107 bytes
```
a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))
```
* Non-competing, this is not the iterative translation of my last submission, just another direct algerbraic method, it sums up all binary-logs of all prime factors, kinda ambiguous to illustrate.
* I will golf this more when i have time.
[Answer]
# MATL, ~~17~~ 16 bytes
```
`tttYfl)/-tq]vnq
```
[**Try it Online**](http://matl.tryitonline.net/#code=YHR0dFlmbCkvLXRxXXZucQ&input=MzA)
**Explanation**
```
        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result
```
[Answer]
# C99, ~~62~~ 61 bytes
1 byte golfed off by @Alchymist.
```
f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}  
```
Call as f(x,&y), where x is the input and y is the output.
[Answer]
# Julia, ~~39~~ 36 bytes
```
\(n,k=2)=n%k>0?n>1&&n\-~k:\(n-n/k)+1
```
[Try it online!](http://julia.tryitonline.net/#code=XChuLGs9Mik9biVrPjA_bj4xJiZuXC1-azpcKG4tbi9rKSsxCgpwcmludGxuKFwoNSkpCnByaW50bG4oXCgzMCkpCnByaW50bG4oXCgzMSkpCnByaW50bG4oXCgzMikpCnByaW50bG4oXCgxMDApKQpwcmludGxuKFwoMjAwKSk&input=)
[Answer]
# Clojure, ~~116~~ 104 bytes
```
(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))
```
-12 bytes by filtering a range to find multiples, then using `last` one to get the greatest one
Na√Øve solution that basically just solves the problem as it's described by the OP. Unfortunately, finding the greatest divisor alone takes up like half the bytes used. At least I should have lots of room to golf from here.
Pregolfed and test:
```
(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))
(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))
(sub-great-divide 30)
30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6
```
[Answer]
# [Perl 6](http://perl6.org/), 35 bytes
```
{+({$_ -first $_%%*,[R,] ^$_}...1)}
```
[Try it online!](https://tio.run/nexus/perl6#y61UUEtTsP1fra1RrRKvoJuWWVRcoqASr6qqpRMdpBOrEKcSX6unp2eoWfu/OLFSIU3B1JoLwjA2gLMM4SwjGMvQAC5tBGT@BwA "Perl 6 ‚Äì TIO Nexus")
### How it works
```
{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), ~~9~~ 7 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
√Öiw^√Ö‚ô´‚îå
```
[Run and debug it](https://staxlang.xyz/#p=8f69775e8f0eda&i=5%0A30%0A31%0A32%0A100%0A200&m=2)
These two operations are identical.
1. Take the biggest divisor of `n` ‚Äì which is different from `n` itself ‚Äì and subtract it from `n`.
2. Let `d` be the smallest prime divisor of `n`. Calculate `n * (d - 1) / d`.
I like #2 better, so let's count how many times we can do that one instead. So at each step, we decrement the smallest prime factor.
Let's work an example starting with 30.
```
Step    n   Factors             Operation
0       30  [2, 3, 5]           Replace 2 with 1
1       15  [1, 3, 5] = [3, 5]  Replace 3 with 2
2       10  [2, 5]              Replace 2 with 1
3       5   [1, 5] = [5]        Replace 5 with 4
4       4   [4] = [2, 2]        Replace 2 with 1
5       2   [1, 2] = [2]        Replace 2 with 1
6       1   [1] = []            End of the line
```
From the example we can see a recursive definition for `steps(x)` that solves the problem. Presented here in python-ish pseudo-code.
```
def steps(n):
    pf = primeFactors(n)
    return sum(steps(d - 1) for d in pf) + 1
```
The stax program, unpacked into ascii looks like this.
```
Z       push a zero under the input
|fF     for each prime factor of the input, run the rest of the program
  v     decrement the prime factor
  G     run the *whole* program from the beginning
  +^    add to the running total, then increment
```
[Run this one](https://staxlang.xyz/#c=Z+++%09push+a+zero+under+the+input%0A%7CfF+%09for+each+prime+factor+of+the+input,+run+the+rest+of+the+program%0A++v+%09decrement+the+prime+factor%0A++G+%09run+the+*whole*+program+from+the+beginning%0A++%2B%5E%09add+to+the+running+total,+then+increment&i=5%0A30%0A31%0A32%0A100%0A200&m=2)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
√Ü·∏å·πÄ·∫°∆ä∆¨L‚Äô
```
[Try it online!](https://tio.run/##y0rNyan8//9w28MdPQ93NjzctfBY17E1Po8aZv4/3P6oac3//6Y6CsYGQGwIxEY6CoYGQI6RgQEA "Jelly ‚Äì Try It Online")
A different approach that takes advantage of Jelly's newer features.
## How it works
```
√Ü·∏å·πÄ·∫°∆ä∆¨L‚Äô - Main link. Takes n on the left
    ∆ä    - Group the previous 3 links as a monad f(n):
√Ü·∏å       -   Proper divisors of n
  ·πÄ      -   The largest
   ·∫°     -   Absolute different with n
     ∆¨   - Repeatedly run f(n) on n, updating n with the result, until
             reaching a fixed point (1), collecting intermediate steps
      L  - Take the length
       ‚Äô - Decrement to account for the 1
```
]