최대공약수 활용문제

최대공약수의 문제유형 

1. 똑같이 나누는 문제 , 크기를 쪼개는 문제 

2. 가능한 가장 큰 또는 많은 수 

3. 문제에서 주어진 숫자보다 더 작은 수를 구하는 경우 

 

문제1)

가로 길이가 18cm, 세로 길이가 20cm인 벽에 남는 부분이 없도록 크기가 같은 타일을 붙이려고 한다. 

가능한 한 큰 정사각형 모양의 타일을 사용하려고 할 때, 타일의 한 변의 크기를 구하여라. 

 

유클리드 호제법을 이용한 최대 공약수 구하기)

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
        
		// 1. 두개의 자연수를 입력받기 
		int a = sc.nextInt(); // ex) 2
		int b = sc.nextInt(); // ex) 6
		
        // 2. a가 b보다 작을때 a와b의 값을 서로 바꿔줌 
		if(a<b){
			int temp = a; 			
			a = b; 
			b = temp; 
		}		
		int r = a%b; // a를 b로 나눈 나머지를 구함(나머지 초기값 설정)  
		
        // 3.a를 b로 나누었을때 나머지가 0이 되면 반복문 탈출 
		while(r != 0) {
			a = b;
			b = r;
			r = a%b; 
		}
		
        // 4.최대 공약수 출력 
		System.out.println(b); 
			
	}

}

 

재귀함수로 유클리드 호제법 사용해서 푸는 방법)

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		// 1.두개의 자연수를 입력받기 
		int a = sc.nextInt(); // ex) 2
		int b = sc.nextInt(); // ex) 6		
		
		// 나누는 자연수(b)가 나누어지는 자연수(a)보다 크면 안됨 
		if(a<b){
			int temp = a; 			
			a = b; 
			b = temp; 
		}		
				
		// 2.재귀함수로 유클리드 호제법을 이용한 최대공약수 구하기 
		recursive(a, b);
		
		System.out.println(b);		
	}
	
	public static int recursive(int a,int b) {
		if(a%b == 0) return b;
				
		return recursive(b,a%b);	
	}

}

 

 

유클리드 호제법 참고 : https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/ 

유클리드 호제법이란? - Lonpeach 기술 블로그 | Lonpeach Tech