LCM
-
최대공약수와 최소공배수 (+ 소수)Algorithm\자료구조 2021. 9. 4. 09:37
1. 최대공약수 (Greatest Common Divisor) - 나눈 값이 0보다 클때까지 반복 (유클리드 호제법 사용) - 알고리즘 예시 : public static int gcd(int a, int b) { if(b == 0) return a; else { int tmp = b; b = a % b; a = tmp; return gcd(a, b); } } 2. 최소공배수 (Least Common Multiple) - 최대공약수와의 관계를 이용해서 구함 - 알고리즘 예시 : public static int lcm(int a, int b) { return ((a * b) / gcd(a, b)); } 3. 소수 (Prime Number) - "1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰자연..