[Algorithm] 코드로 최대공약수(GCD)와 최소공배수(LCM) 구하기

업데이트(2018.04.29) : a mod b 부분 추가

유클리드 호제법을 통해서 최대공약수를 공하고 최대공약수를 통해서 최소공배수를 구해보자


환경 및 선수조건

  • C++


최대공약수 공식(유클리드 호제법)

  • a,b : 최대공약수를 구하고자 하는 두 수
  • r : a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
  • 식 : gcd(a,b) = gcd(b,r)


코드(최대공약수)

example.cpp

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


최소공배수 공식(최대공약수를 이용)

  • a,b : 최소공배수를 구하고자 하는 두 수
  • gcd(a,b) : a와b의 최대공약수
  • (최소공배수 * 최대공약수 = a * b)를 이용
  • 식 : a * b / gcd(a,b)


코드(최소공배수)

example.cpp

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

int lcm(int a, int b){
    return a * b / gcd(a,b);
}


참고자료

  • 코드플러스 알고리즘 기초 강의

[Python] pdb를 이용해 파이썬 코드 디버깅하기

> pdb를 이용해 python 코드를 디버깅하는 방법을 알아보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Python## pdb### pdb란?- ```pdb``` : 파이썬 디버깅 도구로 파인썬 인터프리터...… Continue reading