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

최대공약수(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);
	}