최대공약수를 구하는 방법은 아래와 같다.
n1과 n2를 동시에 나눠줄 수 없을 때 까지 계속 나눠주는 방식을 사용한다.
이때 프로그래밍 언어 특성 상 계속 나눠주는 방식 보단 n1과 n2 중 작은 수부터 나눠 떨어지는 수를
최대 공약수로 사용해야한다.
최소공배수는 (n1 / 최대 공약수) * (n2 / 최대 공약수) * 최대공약수 를 사용하면 구할 수 있다.
이러한 공식의 근거는 최대 공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수이기 때문이다.
#include <iostream>
using namespace std;
int main(){
int n1,n2;
cin>>n1>>n2;
unsigned long max, min;
int t = 0;
if(n1>n2) t = n2;
else t = n1;
for(int i =t;i>0;i--){
if(n1%i==0&&n2%i==0){
max = i;
break;
}
}
min = (n1/max) * (n2/max) * max;
cout << max <<'\n';
cout << min <<'\n';
}
'Baekjoon Review' 카테고리의 다른 글
[Silver 5] 1181번 단어 정렬 (0) | 2023.10.03 |
---|---|
[Silver 4] 1018번 체스판 다시 칠하기 (0) | 2023.10.03 |
[Bronze 1] 1546번 평균 (2) | 2023.10.02 |
[Bronze 1] 1157번 단어 공부 (0) | 2023.10.02 |
[Bronze 1] 1259번 팰린드롬수 (0) | 2023.10.02 |