유클리드 호제법을 간단하게 알아보자.

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다.

 

호제법이란 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 방법을 말합니다.

 

 

구현과정

import java.util.*;
public class Main{
	public static int gcd(int a, int b) {              //유클리드 호제법
		if(b==0)
			return a;
		else
			return gcd(b,a%b);
	}
	
	public static int lcm(int a, int b) {
		return a*b/gcd(a,b);
	}
	
	public static void main(String[] args) {	
		Scanner scan= new Scanner(System.in);
		int a= scan.nextInt();
		int b= scan.nextInt();
		int gcd=0;
		int lcm=0;
		
		if(a<b) {
			int temp=a;
			a=b;
			b=temp;
		}
		
		/*for(int i=b; i>=1; i--) {      //원래의 방법
			if(b%i==0 && a%i==0) {        //최대공약수
				gcd=i;
				break;
			}
		}	
		lcm=a*b/gcd;          //최소공배수
		
		System.out.println(gcd);
		System.out.println(lcm); */
		
		System.out.println(gcd(a,b));
		System.out.println(lcm(a,b));
		}
		}