[Javascript] 최대공약수 알고리즘 (with 유클리드 알고리즘)
참고사이트
최대공약수(GCD, Greateast Common Division)
최소공배수(LCM, Least Common Multiple)
최대공약수 : 두 수를 소인수분해를 한 뒤,
두 수의 공통된 소인수를 모두 곱하면 최대공약수
최소공배수
두 수의 모든 소인수를 곱하기
벤다이어그램으로 볼때
두 수 A,B의 최대공약수를 G 최소공배수를 L이라고하면 다음 식이 성립한다.
AB = LG
벤다이어그램에서 이유를 찾을 수 있다.
A와B를 곱하면 교집합이아닌부분은 한번곱해지고 교집합은 두번 곱해진다
LG도 위와같다.