https://www.acmicpc.net/problem/2609
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static int gcd(int a, int b){
if(b==0) return a;
else return gcd(b, a%b);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int gcd = gcd(a,b);
System.out.println(gcd);
System.out.println(a*b/gcd);
}
}
유클리드 호제법
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 6588번- 골든바흐의 추측 (0) | 2022.10.09 |
---|---|
[JAVA] 백준 1676번 - 팩토리얼 0의 개수 (1) | 2022.10.09 |
[JAVA] 백준 11656번- 접미사 배열 (0) | 2022.10.09 |
[JAVA] 백준 10820번- 문자열 분석 (0) | 2022.10.09 |
[JAVA] 백준 17298번- 오큰수 (0) | 2022.10.09 |