gcd와 lcm

개념

1. gcd
   • greatest common divisior
   • 두 수(혹은 그 이상) 의 공통 약수 중 최대인 것
2. lcm
   • least common multiple
   • 두 수(혹은 그 이상) 의 공통 배수 중 최소인 것
3. 약수(divisor)
   • a를 b로 나누었을때 나머지가 0이면 b는 a의 약수

일반 for문으로 gcd와 lcm 구하기

1. gcd

    a=10
    b=12
    
    for i in range(min(a,b),0,-1):
    	if a%i ==0 and b%i ==0:
    		print(i)
    		break

2. lcm

    a=10
    b=12
    
    for i in range(max(a,b),(a*b)+1):
    	if i%a ==0 and i%b ==0:
    		print(i)
    		break

유클리드 호제법으로 gcd, lcm 구하기

1. 유클리드 호제법
   1. 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 정의하였을 때, A와 B의 최대공약수는 R과 B의 최대공약수와 같음.
   2. 유클리드 호제법을 통해 gcd를 구할 수 있다.
   3. lcm은 두 수를 곱한 값을 gcd로 나눈 몫이다

2. gcd

    a=10
    b=12
    
    #최대공약수
    def gcd(x,y):
        if x%y==0:
            return y
        return gcd(y,x%y)

3. lcm

    a=10
    b=12
    
    #최대공배수
    def lcm(x,y):
        return x*y // gcd(x,y)