[JAVA] 백준 수학 연습문제 - BOJ 2004

BOJ2004.java - 최대 20억의 조합에서 0갯수 찾기, 시간초과 해결

NumbersPrime메서드를 간략하게 바꿈.

원하는 소수로 나누기를 하고 몫을 취합한다.

이 소수의 제곱수로 반복하고, 제곱수가 나눠지는 수를 초과하면 멈춘다.

import java.util.Scanner;
public class BOJ2004 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n=sc.nextLong();
        long m=sc.nextLong();
        long primeTwo=0;
        long primeFive=0;

        primeTwo+= (NumbersPrime(n,2)- NumbersPrime(n-m,2)- NumbersPrime(m,2));
        primeFive+= (NumbersPrime(n,5)- NumbersPrime(n-m,5)- NumbersPrime(m,5));

        System.out.println(Math.min(primeTwo,primeFive));
    }
    public static long NumbersPrime(long x, int prime){
        long sum=0;
        for(long i=prime;i<=x;i*=prime){
            sum+=x/i;
        }
        return sum;
    }
}