목록Data science/Math (1)
DataScience
[Math] 최대공약수와 최소공배수 이론 및 문제풀이
1. 약수와 배수 정의 공약수 : 두 정수의 공통 약수를 공약수라고 한다. 공배수 : 두 정수의 공통 배수를 공배수라고 한다. 2. 최대공약수와 최소공배수 정의 최대공약수[GCD} : 두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다. 최소공배수[LCM] : 양의 공배수 중 가장 작은 것을 최소공배수라고 한다. 위의 식을 보면 최소공배수를 구할때 최소공약수만 계산하면 쉽게 구할수 있는것을 알수 있다. 특히 최소 공약수의 경우 유클리드 호제법을 사용하면 소인수분해를 하지 않고도 계산이 가능하다. 4. 유클리드 호제법 유클리드 호제법은 두 수의 최대 공약수를 구할 때 사용하는 방법이다. 일반적으로 최대 공약수를 구할때는 소인수 분해를 이용한 공통된 소수들의 곱으로 표현하지만 유클리드 호제법은 MOD연산..
Data science/Math
2022. 10. 10. 20:22