최대공약수, 최소공배수 구하기: 유클리드 호제법

a>b 일 때, a를 b로 나눈 나머지 r(mod b)를 구한다.
a에 b, b에 r을 계속 넣다가 r이 0이 되는 순간 y값이 최대공약수다.

무조건 큰 수가 앞에 와야 하는 줄 알고 코드에 swap 함수를 구현했는데 없어도 잘 동작한다고 한다.

C

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
	
	int a, b, rst;

	printf("두 수를 공백을 두고 입력하십시오: ");
	scanf("%d %d", &a, &b);

	rst = gcd(a, b);
	printf("%d\n", rst);

}

C++

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << "\n";
    return 0;
}

C++ 라이브러리 사용

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << "\n";
    return 0;
}

최소공배수는 최대공약수로 두 수의 곱을 나누면 된다.

C

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
	
	int a, b, rst;

	printf("두 수를 공백을 두고 입력하십시오: ");
	scanf("%d %d", &a, &b);

	rst = a * b / gcd(a, b);
	printf("%d\n", rst);

}