Prime factorisation method for nCr
closed account (i351AqkS)
Can anyone help with the code to calculate nCr by reducing the expression to prime factors?
What have you tried so far? What expression are you referring to? I honestly don't see how calculating (n choose k, also known as nCr) relates to prime numbers.
https://en.wikipedia.org/wiki/Combination
When you write nCr in terms of factorials, you can cancel out the common factors from both the numerator and the denominator. (But again, that doesn't necessarily relate to prime numbers.)
Edit:
It sounds like Legendre's formula is the solution to what your problem is gravitating you towards:
https://en.wikipedia.org/wiki/Legendre%27s_formula
Note that the sum is actually finite because eventually all terms will round to 0 once they become less than 1.
Does the Alternate Form help in your situation?
https://math.stackexchange.com/a/1468557/558960
See also: https://www.quora.com/How-do-I-Compute-the-prime-factors-of-the-binomial-coefficient-of-a-number-N-efficiently
https://en.wikipedia.org/wiki/Combination
When you write nCr in terms of factorials, you can cancel out the common factors from both the numerator and the denominator. (But again, that doesn't necessarily relate to prime numbers.)
Edit:
It sounds like Legendre's formula is the solution to what your problem is gravitating you towards:
https://en.wikipedia.org/wiki/Legendre%27s_formula
Note that the sum is actually finite because eventually all terms will round to 0 once they become less than 1.
Does the Alternate Form help in your situation?
https://math.stackexchange.com/a/1468557/558960
See also: https://www.quora.com/How-do-I-Compute-the-prime-factors-of-the-binomial-coefficient-of-a-number-N-efficiently
Last edited on
Topic archived. No new replies allowed.