gcd와 lcm

Konseo·2023년 8월 3일
0

알고리즘

목록 보기
3/21

개념

  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
  1. 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로 나눈 몫이다
  1. gcd
    a=10
    b=12
    
    #최대공약수
    def gcd(x,y):
        if x%y==0:
            return y
        return gcd(y,x%y)
  1. lcm
    a=10
    b=12
    
    #최대공배수
    def lcm(x,y):
        return x*y // gcd(x,y)
profile
둔한 붓이 총명함을 이긴다

0개의 댓글