Can a binominal (or multinomial) coefficient be computed efficiently? It would seem that a preceding query would be on point, but not really for me.  One of the answers comes close, but it isn't complete as is.  Since the answer is going to be an integer, all the factors in the denominator will cancel.  Prime factors can be eliminated by any factor in the numerator that is a multiple.  The problem is composites; canceling them out may involve multiple numerator factors that share primes.  And there's the auxiliary problem of determining prime factors from composite ones (i.e. which composite factor(s) in the numerator should I cancel a composite factor in the denominator against).
I'm thinking of an analogy with computing the greatest common divisor of two positive integers.  You could determine GCD by breaking both arguments into their prime factorizations, then use the minimum exponent for each prime.  But using something like Euclid's algorithm is a lot easier.  For a multinomial coefficient, I could run a Sieve of Eratosthenes up to the numerator's maximum factor, use that table to get all the applicable prime factorizations, then do a bunch of cancelling, but that seems like a lot of work.  Is there a procedure similar to Euclid's GCD one that we can make for binomial coefficients?
 A: Perhaps what you are looking for is Kummer's theorem. From the Wikipedia article:

Kummer's theorem states that for given integer $\,n\ge m\ge 0\,$ and a
  prime number $\,p\,$, the $p$-adic valuation $\,\nu_p({n \choose m})\,$
  is equal to the number of carries when $\,m\,$ is added to $\,n-m\,$ in
  base $\,p.\,$

All that is now needed to calculate $\,N:={n\choose m}\,$ is 
the list of all primes $\,p\le n\,$ and thus
$$ N = \prod_{p\le n} p^{\nu_p(N)}. $$
It is well known (see multinomial theorem) that any multinomial coefficient is a
product of binomial coefficients and thus the $p$-adic valuation of a
multinomial coefficient is the sum of $p$-adic valuations of some
well defined binomial coefficents.
Of course, there are more elementary ways to compute binomial coefficients
without depending on prime factorizations. Just use one of several kinds
of recurrence relations. It all depends on your use case.
A: If you want to do this fast, use prime factorisation, Kummer's theorem, and a balanced multiplication strategy. See e.g. https://codegolf.stackexchange.com/q/37270/194
If you want to keep it simple, the decomposition $$\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$$ and variants give some simple loops which don't require keeping track of what to cancel. E.g.
result = 1
for i = 0 to k-1:
    result = result * (n-i) / (i+1)

