[백준 1934번 C/C++] 최소공배수

 

 

목차

 

 

---

 

 

[백준 1934번 C/C++] 최소공배수 

 

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

---

 

 

코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
using namespace std;

vector<int> v;

int main() {
	int t, a, b, cf;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) 
	{
		cf = 1;
		scanf("%d %d", &a, &b);

		if(a>b)
		{
			for (int j = b; j >= 1; j--)
			{
				if (a % j == 0 && b % j == 0)
				{
					cf *= j; //공약수를 곱해 최대공약수를 구함. 
					a /= j;
					b /= j;
				}
			}
		}
		else
		{
			for (int j = a; j >= 1; j--)
			{
				if (a % j == 0 && b % j == 0)
				{
					cf *= j; //공약수를 곱해 최대공약수를 구함. 
					a /= j;
					b /= j;
				}
			}
		}

		v.push_back(a * b * cf);
	}

	for (int i = 0; i < v.size(); i++)
		printf("%d\n", v[i]);

	return 0;
}

시간 140m/s

느리다.

 

아래에 더 나은 코드가 있다.

 

---

 

더 나은 풀이 

 

#include <stdio.h>
int GCD(int a, int b)
{
    return b ? GCD(b, a%b) : a;
}

int main()
{
    int T, A, B;
    scanf("%d", &T);
    
    while (T--)
    {
        scanf("%d %d", &A, &B);
        printf("%d\n", A*B / GCD(A, B));
    }
}

유클리드 호제법으로 최대공약수를 구한다.

 

최소공배수 = A * B / 최대공약수

 

 

위의 코드는 시간 0m/s

 

https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/

유클리드 호제법이란? | Lonpeach Tech

 

---