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!.

Pyth, 11 bytes

fq1=-Q/QhPQ

Test suite

A straightforward repeat-until-true loop.

Explanation:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy:
         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.

Pyth - 15 14 13 bytes

Special casing 1 is really killing me.

tl.u-N/Nh+PN2

Try it online here.

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.

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.

Python, 50 48 bytes

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)

Return True for n=2, if that's okay. This isn't going to finish that last test case any time soon...

Alternatively, a 49-byte which returns 1 for n=2 (Python 2 only):

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

Pyth, 17 16 bytes

L?tbhy-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)

Original 17 bytes:

L?tb+1y-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)

(I actually answered that question with this Pyth program.)

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.

><>, 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.

Matlab(58)

  function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end

C99, 62 bytes

f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%b||(++*c,b=a-=b))b--;}  

Call as f(x,&y), where x is the input and y is the output.

Haskell, 65 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 ==.

Retina, 26

.+
$*
+`\b(1+)(\1+)$
,$2
,

Try it online - 1st line added to run all testcases in one go.

Sadly this uses unary for the calculations, so input of 2016¹⁵⁵ is not practical.

• The first stage simply converts the decimal input to unary as a string of 1s
• The second stage calculates the largest factor of n using regex matching groups and effectively subtracts it from n. It also prepends a , to the pattern space. The + config causes this stage to repeat until there are no more changes. Thus the result is a number of , corresponding to the number of operations
• The final stage simply counts and returns the number of ,.

Matlab(129)

  a=input('');c=[];b=factor(a);while(b~=1)f=sort(b);t=f(1:end-1);c=[c,t,2-(b(1)==a(1))];b=factor(max(b)-1);end,sum(fix(log2(c)))+1

• 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-1) of (maximums of factors -1) , kinda ambiguous to illustrate.