[Java] 최대공약수와 최소공배수

 

자바를 공부하다보면 단골손님으로 두 수의 최대공약수와 최소공배수를 구하는 문제가 자주 등장한다. 아래 준비한 예제는 두 수를 입력받고 두 수의 최대공약수와 최소공배수를 구하는 문제이다.

 

 

➰최대공약수 구하기

package Test;

import java.util.Scanner;

public class Arr_02 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 두 수를 입력받아 두 수의 최대 공약수 구하기
		System.out.print("num1 = ");
		int num1 = scan.nextInt();
		System.out.print("num2 = ");
		int num2 = scan.nextInt();
		
		int gcd = 0;	//최대공약수
		int min = 0;
		if(num1 <num2) {
			min = num1;
		}else {
			min = num2;
		}
		
		for(int i=1; i<=min; i++) {
			if(num1 % i == 0 && num2 % i == 0) {
				gcd = i;
			}
		}
	}
}

 

 

 

 

➰최소공배수 구하기

package Test;

import java.util.Scanner;

public class Arr_02 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 두 수를 입력받아 두 수의 최소 공배수 구하기
		System.out.print("num1 = ");
		int num1 = scan.nextInt();
		System.out.print("num2 = ");
		int num2 = scan.nextInt();
		
		int lcm = 0, min = 0;
		int gcd = 0;
		
		if(num1 <num2) {
			min = num1;
		}else {
			min = num2;
		}
		
		for(int i=1; i<=min; i++) {
			if(num1 % i == 0 && num2 % i == 0) {
				gcd = i;
			}
		}
		lcm = num1 * num2 / gcd;	//최소공배수
	}
}

** 최소공배수는 처음 예제처럼

    1)  최대공약수를 구하고,

    2)  num1과 num2를 곱한 후,

    3)  최대공약수로 나누면 된다.

 

 

 

---

 

 

그럼 최소공배수와 최대공약수를 구하는 법을 알았으니 간단한 예제를 풀어보자.

 

 

문제1) 연필 42자루와 지우개 28개를 최대한 많은 학생에게 남김없이 똑같이 몇 명까지 나누어 줄 수 있는가? (최대공약수)

 

 

 

 

문제2) 가로가 12 이고 세로가 8인 직사각형 모양의 종이를 늘어놓아 만들 수 있는 가장 작은 정사각형을 만들려고 한다. 직사각형은 몇 장이 필요한가? (최소공배수)