[JAVA] 최소공배수, 최대공약수 - 유클리드 호제법

💡문제 상황

두 정수의 최대 공약수와 최소 공배수를 출력

 

=> 최대 공약수

 : 0이 아닌 두개 이상의 정수의 공통되는 약수 중에서 가잘 큰 수

즉, 두 정수 a,b의 공약수 중에서 가장 큰 수 

 

=> 최소 공배수 

 :  0이 아닌 두 개 이상의 정수의 양의 공배수 중에서 가장 작은 수

 

💡내 풀이

Scanner sc = new Scanner(System.in);

a = sc.nextInt();
b = sc.nextInt();

int min = (a < b )? a : b ;
int gcd = 0 ; // 최대 공약수

for (int i = 1; i < min; i ++){
	if(a % i == 0 && b % i == 0){
    	gcd = i ;
     }
}
int max = 0; //최소 공배수
max = a*b/gcd;

👉 for 문은 정수이므로 1부터 시작해서 둘중에 작은 수 까지만 순회하기 

👉 만약 i로 a와b를 나눴을 때 둘다 나머지가 없으면 최대공약수 

 

 

💡유클리드 호제법

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.
호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냄.

static int gdc(int a, int b) { //최대 공약수
		if(a<b) // 유클리드 호제법 조건
		{
			int temp = a;
			a = b;
			b = temp;
		}
		while(b!=0) { // 유클리드 호제법
			int r=a%b;
			a=b;
			b=r;
		}
		return a;
	}
	
	static int lcm(int a, int b) { //최소 공배수
		return a*b / gdc(a,b);
	}

👉가장 기본적인 방법이라는데 이해하기는 어렵다..ㅠ

👉 쉽게 보면 큰 숫자를 작은 숫자로 나누고 그 나머지로 작은 숫자를 나누는 계산을 나머지가 0이 될때까지 반복하는 것