n!의 소인수분해

n이 작은 수라면 충분히 손으로 구할 수 있다. 예를 들어 10! = 1*2*3*4*5*6*7*8*9*10이므로 1*2*3*(2*2)*5*(2*3)*7*(2*2*2)*(3*3)*(2*5) 이렇게 각각의 n들을 소인수분해한 것의 곱으로 표현할 수 있다. 정리하면 (2^8)*(3^4)*(5^2)*(7^1) 이렇게 나온다. 하지만 n이 100만 되더라도 일일이 구하는 것이 힘들어보인다. 특히 백준 문제에서 n의 범위가 10억까지도 주어지기 때문에 선형적으로 일일이 확인하기는 쉽지 않아 보인다. 1 2 3 4 5 6 7 8 9 10 2 3 2 5 2 7 2 3 2 2 3 2 3 5 2 10!에서 소인수분해를 하기 위해서는 결론적으로 10! = (2의 p승) * (3의 q승) * (5의 r승) * (7의 s승) 의 p, q, r, s만 구하면 된다. p만 구해봐도 나머지는 어떻게 구하는지 바로 알 수 있다. 1 2 3 4 5 6 7 8 9 10 합계 2 3 2 5 2 7 2 3 2 5 2 3...

원문링크 : n!의 소인수분해