EuclideanAlgorithm

package k20231205;

 

import java.util.Scanner;

 

public class EuclideanAlgorithm {

 

public static void main(String[] args) {

 

Scanner scanner = new Scanner(System.in);

// 최대공약수, 최소공배수 판단할 숫자 2개를 입력한다

System.out.println("숫자 2개를 입력하세요: ");

int a = scanner.nextInt();

int b = scanner.nextInt();

 

// 입력받은 숫자 대소구분

int big;

int small;

if (a>=b) {

big=a;

small=b;

} else {

big=b;

small=a;

}

System.out.printf("큰 수: %d, 작은 수 : %d\n", big, small);

// 입력받을 숫자의 크기에 따라서 나눗셈 연산을 실행하는 횟수가 다르므로 무한 루프를 돌려서 처리한다

while (true) {

// 큰 수를 작은 수 로 나눈 나머지를 계산한다.

int r = big % small;

 

// 나머지가 0이면 무한루프를 탈출한다

if (r==0) {

break;

}

// 나머지가 0이 아니면 큰 수를 기억하던 기억장소에 작은 수 를 넣어주고 작은 수를 기억하던 기억장소에 나머지를 넣어준다

big = small;

small = r;

}

// 최대공약수, 최소공배수를 출력한다.

System.out.printf("최대공약수: %d, 최소공배수: %d\n", small, a*b/small);

}

}