밍의 기록들😉

[수학] 최대공약수(GCD)와 최소공배수(LCM) 구하기 본문

자료구조, 알고리즘/기본다지기

[수학] 최대공약수(GCD)와 최소공배수(LCM) 구하기

민쓰 2018. 8. 10. 19:44

최대공약수(GCD)

  • 두 수의 공통된 약수 중에서 가장 큰 정수
  • 최대공약수가 1인 두 수는 서로소
코드
	private  int gcd(int a, int b) {
		if(b==0){
			return a;
		}
		else{
			return gcd(b, a%b);
		}
	}

  • 유클리드 호제법
  • a를 b로 나눈 나머지 r
  • GCD(a,b) = GCD(b,r)
  • r = 0 일 때 b가 최대공약수
재귀함수 사용하여 구현한 코드
	private  int gcd(int a, int b) {
		if(b==0){
			return a;
		}
		else{
			return gcd(b, a%b);
		}
	}
재귀함수 사용하지 않고 구현한 코드
		private  int gcd(int a, int b) {
		while(b !=0){
			int r = a%b;
			a = b;
			b = r;
		}
		return a;
	}



최소공배수(LCM)

  • 두 수의 공통된 배수 중에서 가장 작은 정수
  • 최대공배수는 GCD를 응용해서 구할 수 있음
  • 최소공배수 l = g * (a/g) * (b/g)
코드
			
private  int lcm(int a, int b) {
		int g = gcd(a,b);
		return g*(a/g)*(b/g);
	}


0 Comments
댓글쓰기 폼