여기서 우리는 임의의 수의 계승 결과에 대해 후행 0의 수를 계산하는 방법을 볼 것입니다. 따라서 n =5이면 5입니다! =120. 뒤에 오는 0은 하나만 있습니다. 20!의 경우 4개의 0이 20이 됩니다! =2432902008176640000.
가장 쉬운 방법은 계승을 계산하고 0을 계산하는 것입니다. 그러나 이 접근 방식은 n의 값이 크면 실패합니다. 그래서 우리는 다른 접근 방식을 따를 것입니다. 소인수가 2와 5인 경우 후행 0이 있을 것입니다. 2와 5를 계산하면 결과를 얻을 수 있습니다. 이를 위해 우리는 이 규칙을 따를 것입니다.
후행 0 =factorial(n)의 소인수에서 5의 개수
알고리즘
countTrailingZeros(n)
begin count := 0 for i := 5, (n/i) >= 1, increase i := i * 5, do count := count + (n / i) done return count; end
예시
#include <iostream> #include <cmath> #define MAX 20 using namespace std; int countTrailingZeros(int n) { int count = 0; for (int i = 5; n / i >= 1; i *= 5) count += n / i; return count; } main() { int n = 20; cout << "Number of trailing zeros: " << countTrailingZeros(n); }
출력
Number of trailing zeros: 4