유클리드 호제법
최대공약수
두 개의 자연수 a와 b에서 (단 a>b ) a를 b로 나눈 나머지를 r이라 했을 때
GCD(a,b) = GCD(b,r) 과 같고, r이 0이면 그때 b가 최대 공약수이다.
fun GCD(val a: Int, val b:Int){
if(b==0) return a
else return GCD(b,a%b)
}
Kotlin
복사
최소공배수
•
두 수의곱 / 최대공약수
fun LCM(a: Int, b: Int){
return a*b / GCD(a,b)
}
Kotlin
복사
가함을 알 수 있음
근데 중요한 점이 입력값이 25일 때 카운트가 2가 증가한다는 점이다.
→ 25가 소인수 분해로 5^2 이기 때문 (5가 2번 증가함)
일반적으로 소인수 분해에서 5가 증가하는 원인은 5의 배수의 숫자가 들어간 경우이다.
기본적으로 2의 팩토리얼 개수는 5의 팩토리얼개수보다 많다 그러면 5의 팩토리얼 개수를 카운트
하면 뒷자리 0의 개수를 알 수 있다는 의미이다.