[백준 2609 C++] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제

* 두 수의 최대공약수와 최소공배수를 찾은 문제

 

풀이

* num1 과 num2를 i로 나누어 본다.

  i는 2부터 시작해서 점점 커지다가

  나머지가 0이되는 구간을 만나면 

  i는 다시 2부터 시작한다.

 

* i가 점점 커지다가 num1과 num2보다 커지면 더이상 약수가 없다는 의미.

 

* 출력한다.

 

생각할 점

* 

 

코드

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

int main() {
	int num1, num2, GCF = 1;
	int num11, num22;

	cin >> num1 >> num2;
	num11 = num1;
	num22 = num2;

	int i = 2;
	while (num1 != 1 && num2 != 1) {
		if (num1 < i && num2 < i)
			break;

		if (num1 % i == 0) {
			if (num2 % i == 0) {
				num1 /= i;
				num2 /= i;
				GCF *= i;
				i = 1;
			}
		}
		i++;
	}

	cout << GCF << endl;
	num11 /= GCF;
	num22 /= GCF;
	cout << num11 * num22 * GCF << endl;

	return 0;
}

 

 

 

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.