개념
- gcd
- greatest common divisior
- 두 수(혹은 그 이상) 의 공통 약수 중 최대인 것
- lcm
- least common multiple
- 두 수(혹은 그 이상) 의 공통 배수 중 최소인 것
- 약수(divisor)
- a를 b로 나누었을때 나머지가 0이면 b는 a의 약수
일반 for문으로 gcd와 lcm 구하기
- 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
- 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 구하기
- 유클리드 호제법
- 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 정의하였을 때, A와 B의 최대공약수는 R과 B의 최대공약수와 같음.
- 유클리드 호제법을 통해 gcd를 구할 수 있다.
- lcm은 두 수를 곱한 값을 gcd로 나눈 몫이다
- gcd
a=10
b=12
def gcd(x,y):
if x%y==0:
return y
return gcd(y,x%y)
- lcm
a=10
b=12
def lcm(x,y):
return x*y // gcd(x,y)