브론즈 1

문제 링크
난이도 : 브론즈 1

문제 내용

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

입력

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

출력

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

문제 분석

원래는 약수들 저장해서 분석하려고 했으나 자꾸 틀렸다고 하길래

유클리드 호제법 찾아봄

두 수 a, b의 최소공배수는 b, b%a의 최소공배수와 같음

최대공약수는 a*b를 최소공배수로 나눈것과 같음

작성한 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int gcd_ab = gcd(a, b);
    int lcm_ab = abs(a * b) / gcd_ab;
    printf("%d\\n%d", gcd_ab, lcm_ab);
}

최대공약수 gcd_ab

최소공배수 lcm_ab로 저장

우수 코드 분석

#include <stdio.h>
 
int main()
{
	int a,b,d;
	scanf("%d %d", &a, &b);
	d=a;
	while(d%b!=0) d+=a;
	printf("%d\\n%d", a*b/d, d);
	return 0;
}

여기서 d가 최대공약수인듯

최대공약수 구하는 방법을 b로 안나눠질때까지 a를 더하는 방법으로 함