백준 2609번: 최대공약수와 최소공배수

백준 2609번: 최대공약수와 최소공배수

 

- 최대공약수와 최소공배수를 구하는 가장 널리 알려진 방법입니다. 이러한 방법을 for문을 이용하여 코드를 만들면 아래와 비슷한 코드를 만드실 수 있을 겁니다. 하지만 시간 초과에 걸려 통과하지 못합니다.

 

	import java.util.Scanner;
	public class Main{
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	boolean tf = false;
	int gcf = 1, lcm = 1;
	int a = sc.nextInt();
	int b = sc.nextInt();
	while(true) {
	for (int i = 2; i < ((a > b) ? b : a); i++) {
	if ((a % i == 0) && (b % i == 0)) {
	a = a / i;
	b = b / i;
	gcf = gcf * i;
	break;
	}
	if(i == ((a > b) ? b-1 : a-1)){
	tf = true;
	break;
	}
	}
	if(tf == true)
	break;
	}
	lcm = gcf * a * b;
	System.out.println(gcf+" "+lcm);
	sc.close();
	}
	}

view raw BOJ_2609_ex.java hosted with ❤ by GitHub

- 이 문제는 "유클리드 호제법"을 사용하여 풀어야 합니다.

유클리드 호제법이란,

두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r < a)라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다.

- 아래 gcd(greatest common divisor) 매소드는 유클리드 호제법을 알고리즘으로 나타낸 것입니다.

  24와 18을 예로 들면,

1.  a = 24, b = 18, tmp = 6   -> a = 18, b = 6
2. a = 18, b = 6, tmp = 0 -> a = 6, b = 0
3. return a = 6

-최소공배수는 최대공약수를 활용하여 쉽게 구할 수 있습니다.

https://terms.naver.com/entry.nhn?docId=3338367&cid=47324&categoryId=47324

- 위 사진을 참고하여 매소드를 만들면 아래의 lcm(least common multiple) 매소드가 됩니다.

 

	import java.util.Scanner;
	public class Main{
	public static int gcd(int a, int b){
	while(b > 0){
	int tmp = b;
	b = a % b;
	a = tmp;
	}
	return a;
	}
	public static int lcm(int a, int b){
	return (a * b) / gcd(a,b);
	}
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int gcd, lcm;
	int a = sc.nextInt();
	int b = sc.nextInt();
	gcd= gcd(a,b);
	lcm = lcm(a,b);
	System.out.println(gcd+" "+lcm);
	sc.close();
	}
	}

view raw BOJ_2609.java hosted with ❤ by GitHub