beaekjoon 2609

백준 2609번

백준 2609번 문제

문제 설명

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

풀이

유클리드 호제법을 사용하여 최대공약수(GCD)를 구하여한다.

유클리드 호제법이란?

MOD연산(나머지 구하기)를 이용한다. 먼저, 큰수를 작은 수로 나눈 나머지를 구한다.

1112와 695를 예로 사용하면

1112 mod 695 = 417

그 다음, 나누었던 수를 나머지와 다시 나머지를 구한다

695 mod 417 = 278

이 과정을 나머지가 0 이 나올때까지 반복한다

417 mod 278 = 139
278 mod 139 = 0

마지막으로 나눈 수인 139가 GCD가 된다.

코드

이과정을 C 언어로 작성하면

# include <stdio.h>

int main()
{
	int num_1, num_2, temp, GCD;
	
    //숫자 입력받기
	scanf("%d %d",&num_1,&num_2); 

    //큰 숫자를 num_1으로 변경
	if(num_1 < num_2)
	{
		temp = num_1;
		num_1 = num_2;
		num_2 = temp;
	}
	
    //유클리드 호제법 사용
	while(num_2!=0)
	{
		temp = num_1%num_2;
		num_1 = num_2;
		num_2 = temp;
		
	}
	
    GCD = num_1;
	printf("%d\n",GCD);
	
	return 0;
}

동일한 과정을 python으로 작성해보면

def gcd(a,b):
    if a<b:
        a , b = b ,a

    while(True):
        temp = a%b
        a ,b = b, temp

        if b ==0:
            break

    return a
#숫자 입력받기
num_1,num_2 = map(int,input().split())

#유클리드 호제법 실행
print(gcd(num_1,num_2))

최소공배수 구하기

num_1 와 num_2의 최소공배수(LCM)는 num_1 와 num_2의 곱을 최대공약수로 나눈값과 같다는 성질을 이용해서 풀 수 있다

이과정을 C 언어로 작성하면

int LCM;
	
LCM = num_1 * num_2 / GCD;
printf("%d\n",LCM);
	
return 0;

동일한 내용을 python으로 정리하면

print(num_1 * num_2 / gcd(num_1,num_2))

최종 코드

C

# include <stdio.h>

int main()
{
	int num_1, num_2, temp, LCM, GCD;
	
	scanf("%d %d",&num_1,&num_2);
	LCM = num_1 * num_2;
	if(num_1 < num_2)
	{
		temp = num_1;
		num_1 = num_2;
		num_2 = temp;
	}
	
	while(num_2!=0)
	{
		temp = num_1%num_2;
		num_1 = num_2;
		num_2 = temp;
		
	}
    GCD = num_1;
	LCM /= GCD;

	printf("%d\n",GCD);
	printf("%d",LCM);

	return 0;
}

Python

def gcd(a,b):
    if a<b:
        a , b = b ,a

    while(True):
        temp = a%b
        a ,b = b, temp

        if b ==0:
            break

    return a

num_1,num_2 = map(int,input().split())
LCM = num_1 * num_2

print(gcd(num_1,num_2))
print(LCM / gcd(num_1,num_2))