[BOJ] 2609번 최대공약수와 최소공배수 / 사용언어 : 파이썬(python)

※ 문제링크

2609번: 최대공약수와 최소공배수

 

해당문제는 두개의 수가 주어졌을때, 두 수의 최대공약수와 최소공배수를 구하는 문제였다.

문제를 해결하기 위해 최대공약수와 최소공배수의 성질을 이용했다.

예시) 18, 24 -> 18 = 2x3x3 / 24 = 2x2x2x3 -> lcm = 2x3(6) / gcf = 2x2x2x3x3(72)

자세한 문제풀이 방식은 아래와 같다.

1. 에라토스테네스의 체를 활용하여 10000이하의 소수리스트 생성

2. 소수리스트를 활용하여 두개의 숫자를 소인수 분해하여 리스트 생성

3. 리스트들을 합쳐서 소인수들을 확인하고 해당 소인수들을 카운트함수를 이용하여 갯수 확인

풀이방법을 구상하고 난 뒤 문제를 푸는 것은 그리 어렵지 않았으며, 문제풀이도 정상적으로 합격하는 것으로

확인하였다. 자세한 코드는 아래와 같다.

 

A, B = map(int, input().split())
check_list = [True] * 10001 # 10000이하의 소수 구하기
def sosu(): 
    sosu_list = []
    for i in range(2, 10001):
        if check_list[i]:
            sosu_list.append(i)
            for k in range(i, 10001, i):
                check_list[k] = False
    return sosu_list

sosu_list = sosu()
def ftr(number, sosu_list):
    r_list = []
    i = 0
    while sosu_list[i] <= number:
        if number % sosu_list[i] == 0:
            r_list.append(sosu_list[i])
            number = number // sosu_list[i]
        else:
            i += 1
    return r_list
list_a = ftr(A, sosu_list)
list_b = ftr(B, sosu_list)
list_ftr = list(set(list_a + list_b))
lcm, gcf = 1, 1 # 최소공배수, 최대공약수 변수선언
for num in list_ftr:
    check1 = list_a.count(num)
    check2 = list_b.count(num)
    if check1 > check2:
        gcf *= (num**check2)
        lcm *= (num**check1)
    else:
        gcf *= (num**check1)
        lcm *= (num**check2)
print(gcf,lcm, sep = '\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.