[수학] python으로 최대공약수, 최소공배수 구하기(사람처럼 생각하기)

0. 목표

 - python으로 최대공약수, 최소공배수 연산

1. 플로우 차트

- 가장 쉬운 방법은 둘 중 작은숫자에서 -1씩 빼면서 나누는 방법이지만... 재미없음.

2. 실습

 1) 최소 숫자 추출

  - 연산 효율 증대 목적

def min_num(a, b):
    if a < b:
        result = a
    else:
        result = b
    return result

 - 테스트

print(min_num(120, 20))

 - 결과

20

 2) 최대공약수 서브연산 모듈

  (1) 1부터 시작해서 최소 숫자까지 수를 올리면서 나눗셈 연산

  (2) 이때 나머지가 둘 다 0이 나오면 해당 수를 첫 번째 몫으로 추출

  (3) 만약 마지막 연산까지 다 돌았을 때, a b에 대한 나머지를 검출하여 0이 아닐 경우 1로 변경(서로소 검출)

  (4) 결과물은 첫 번째 몫과 첫 번째 연산의 각 결과 값

def SubGCD(a, b):
    min_number = min_num(a, b)        
    result = []
    for i in range(1, min_number + 1):
        a_remainder = a % i
        b_remainder = b % i
        if a_remainder + b_remainder == 0:
            if i == 1:
                pass
            else:
                break
        else:
            pass
    a_remainder = a % i
    b_remainder = b % i
    a_quotient = a // i
    b_quotient = b // i
    if a_remainder + b_remainder == 0:
        pass
    else:
        i = 1
    return i, a_quotient, b_quotient

 - 테스트

print(SubGCD(120, 20))

- 결과

(2, 60, 10)

 3) 최대공약수 연산

  (1) 재귀적 방법을 통하여 각 수에 나눈 값중 하나라도 1이 발생할 경우 종료

  (2) 결과값으로는 몫의 리스트 값과 몫을 곱한 값(최대공약수)

def GCD(a, b):
    result = []
    result2 = 1
    while 1:
        tmp, a, b = SubGCD(a, b)
        result.append(tmp)
        result2 = result2 * tmp
        if (a == 1 or b == 1):
            break
        pass
    return result, result2

 - 테스트

print(GCD(120, 20))

 - 결과

([2, 2, 5], 20)

 4) 최소공배수 연산

  (1) 최대공약수 추출

  (2) 각 값을 최대공약수로 나눈 값을 얻음

  (3) 최대공약수 * (2)에서 구한 값

def LCM(a, b):
    _, num_GCD = GCD(a, b)
    a_quotient = a / num_GCD
    b_quotient = b / num_GCD
    result = a_quotient * b_quotient * num_GCD
    return result

 - 테스트1

print(LCM(120, 20))

 - 결과1

120.0

  - 테스트2

print(LCM(120, 21))

 - 결과2

840.0

3. 참고

 - 수학의 정석(10-가)