백준 알고리즘
[Bronze I] 최대공약수와 최소공배수 - 2609
성능 요약
메모리: 13156 KB, 시간: 4 ms
분류
유클리드 호제법, 수학, 정수론
문제 설명
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
use std::io::{BufReader,BufRead,BufWriter,Write,stdin,stdout};
fn main(){
let mut reader= BufReader::new(stdin().lock());
let mut writer= BufWriter::new(stdout().lock());
let mut input = String::new();
reader.read_line(&mut input).unwrap();
let nums: Vec<i32>= input.trim().split_whitespace().map(|x|x.parse().unwrap()).collect::<Vec<i32>>();
writeln!(writer,"{}",gcd(nums[0], nums[1])).unwrap();
writeln!(writer,"{}",lcm(nums[0], nums[1])).unwrap();
writer.flush().unwrap();
}
//최대 공약수를 구하는 함수
fn gcd(mut x: i32, mut y: i32) -> i32 {
//두 수를 나눈 후 나눈 나머지를 구하여 0 이 될 떄까지 반복한다.
while y != 0 {//y가 0이 될떄 x가 Greastest Common Divisor GCD이다.
let remainder = x % y;//x와 y를 나눈 나머지
x = y;//다음 연산에서 r= y % r을 수행해야 하므로
y = remainder;//x에 y를 대입하고 y에 r을 대입한다.
}
x //최대 공약수를 리턴한다.
}
//최소 공배수
fn lcm(a:i32,b:i32)->i32 {
a*b /gcd(a, b)
}
