728x90
import java.util.*;
public class Main {
public static void main(String[] args) {
int a = 8;
int b = 6;
//최대공약수 (유클리드호제법)
System.out.println("최대공약수 : "+gcd(a,b));
//최소공배수 = 0이 아닌 두 수의 곱 / 최대공약수
System.out.println("최소공배수 : "+ (a * b) / gcd(a,b));
}
//최대공약수
public static int gcd(int a, int b)
{
//a에 큰 값 위치 시킴
if(a < b)
{
int temp = a;
a = b;
b = temp;
}
//유클리드 호제법
while(b != 0)
{
int n = a % b;
a = b;
b = n;
}
//b가 0이 되는 순간, a가 두 수의 최대공약수
return a;
}
}
최대공약수 (유클리드 호제법)
- a, b 중 a에 더 큰 값을 위치 시킨다.
- b가 0이 될 때까지 a%b를 반복
- a = b 대입
- b = a%b의 결과 대입
- b = 0이 될 때, a 값 = 최대공약수
최소공배수
최소공배수 = 0이 아닌 두 수의 곱 / 최대공약수
728x90
'Algorithm > 알고리즘 설명' 카테고리의 다른 글
[알고리즘] 위상 정렬 (Topological Sorting) (0) | 2020.09.17 |
---|---|
[알고리즘] 이분 탐색 (Binary Search) (0) | 2020.08.31 |
[알고리즘] 각 자리 수의 합 구하기 (0) | 2020.08.22 |
[알고리즘] 문자열 → int 형 변환 (0) | 2020.08.22 |
[알고리즘] LCS (최장 공통 부분) 찾기 (0) | 2020.08.22 |
댓글