연속된 수의 소인수 분해 빠르게하기, 이항계수

이항계수 nCr에서 끝자리 0의 개수를 출력하는 문제이다. 끝자리 10의 개수를 확인하려면 해당 숫자를 2로 소인수분해, 5로 소인수분해해서 2의 개수와 5의 개수 중 최솟값을 출력하면 된다. 이러한 소인수 분해를 빠르게 하는 방법은 아래와 같다. public static int findTwo(int n) { int cnt = 0; for (long i = 2; n / i >= 1; i *= 2) cnt += n / i; return cnt; } 수를 입력 받아서 n / i가 1보다 크거나 같을 때 까지 i를 2부터 2씩 곱하고 cnt에 n/i를 더해주면 된다. 이렇게 하면 5를 입력 했을 때 4일 때 + 2, 2일 때 +1이 된다. 즉 5를 입력하면 1, 2, 3, 4, 5 중 2의 개수를 빠르게 계산한다. 유의할 점은 i의 범위가 매우 커질 수 있으므로 long으로 선언해줘야한다. 아래는 전체코드이다. import java.io.BufferedReader; import java....

원문링크 : 연속된 수의 소인수 분해 빠르게하기, 이항계수