[Projet Euler 231] 조합의 소인수분해

문제

이항계수 ₁₀C₃ = 120 이다.
120 = 2³ × 3 × 5 = 2 × 2 × 2 × 3 × 5 이고, 2 + 2 + 2 + 3 + 5 = 14 이 된다.
즉 ₁₀C₃ 의 소인수분해하여 나온 인자의 합은 14이다.

_20000000C_15000000 의 소인수분해 인자의 합을 구하라.

http://projecteuler.net/index.php?section=problems&id=231

---

풀이법.

130! 마지막엔 0이 몇 개 있는지를 풀어내는 방법을 응용한다. 사실 동일한 거다.

일반적으로 m! 에 소수 p가 몇 개 있는지 구하는 식은 [m/p] + [m/(p*p)] + [m/(p*p*p)] + [m/(p*p*p*p)] + ... 이다. nCm = n!/((m!)((n-m)!)) 이다.

---

소스.

invalid-file

파이썬 소스다운로드