Baekjoon2609: 최대공약수와 최소공배수

최대공약수와 최소공배수

1 초

128 MB

49754

29452

23917

60.817%

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

풀이

먼저 두 수를 정렬해 작은 수와 큰 수로 분류하고

작은 수에서 계속 1을 빼며 그 수가 두 수의 약수인지 체크,

큰 수에 계속 1,2,3,...을 곱하며 그 수가 두 수의 배수인지 체크한다

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr=new int[2];
		arr[0]=sc.nextInt();
		arr[1]=sc.nextInt();
		int start=0;
		Arrays.sort(arr); //왼쪽에 작은 수, 오른쪽에 큰 수
		while(true) {
			if(arr[0]%(arr[0]-start)==0 && arr[1]%(arr[0]-start)==0) {
				System.out.println(arr[0]-start);
				break;
			}
			start++;
		}
		start=1;
		while(true) {
			if((arr[1]*start)%arr[0]==0) { //arr[1]에 정수를 곱한 수는 이미 arr[1]의 배수이다
				System.out.println(arr[1]*start);
				break;
			}
			start++;
		}
}}