16_백준 _2609번 파이썬 최대공약수와 최소공배수

- 최소공약수는 숫자의 약수를 뽑아내서 리스트로 저장하여 각 리스트에서 가장 큰 값을 리턴하게 만들었고
최대공배수는 그냥 for문으로 입력받은 두 수중 큰 값부터 ~ 둘을 곱한 값 까지 다 돌면서
입력받은 값으로 동시에 나눠질 때를 리턴 하였다.
검색해보니 최소 공약수도 for문 안에 if문으로 동시에 나눠질 때 리던하는 방식이 있었다.
참고 (최대공약수,최소공배수)

 

• 풀이-1

# 최대공약수 함수
def GCD(X, Y):
    if X < Y:
        min = X
    else:
        min = Y
    for i in range(min + 1, 1, -1):
        if X % i == 0 and Y % i == 0:
            res = i
            break
    return res


# 최소공배수 함수
def LCM(X, Y):
    if X < Y:
        max = Y
    else:
        max = X
    for i in range(max, (X * Y) + 1):
        if i % X == 0 and i % Y == 0:
            res = i
            break
    return res

• 풀이-2

# 약수 divisor
a, b = map(int, input().split())


# 약수를 찾아 리스트로 저장
def divisor(x):
    n = 1
    divisors = []
    while n <= x:
        if x % n == 0:
            divisors.append(n)
        n += 1
    return divisors


a_divisor = divisor(a)
b_divisor = divisor(b)


# 최대 공약수 (greatest common divisor)
def greatest_common_divisor(list1, list2):
    for i in range(len(list1)):
        if list1[-1 - i] in list2:
            return list1[-1 - i]
    return -1


# 최소 공배수 (Least Common Multiple)
def least_common_multiple(a, b):
    # for문을 이용한 최소공배수 파이썬 코드
    if a < b:
        max = b
    else:
        max = a
    for i in range(max, (a * b) + 1):
        if i % a == 0 and i % b == 0:
            return i

    return -1


# 최대 공약수 출력
print(greatest_common_divisor(a_divisor, b_divisor))
# 최소 공배수 출력
print(least_common_multiple(a, b))

# 입력
24 18
# 출력
6
72