2520은 1~10까지의 수로 나누어 떨어지는 수 중에서 가장 작은 수다. 그러면 1~20까지의 수로 나누어 떨어지는 가장 작은 수는?

풀이 #1

아주 직관적으로 풀어보았다. 최소공배수와 소인수분해에 대해서 조금 읽어본 다음에 풀게 되었는데, 요는 간단하다.

  1. 1부터 20까지 전부 소인수분해를 해 보고
  2. 1~20의 소인수분해 결과 중 가장 많이 출현한 소수를 곱한다.

이게 되겠다. 예를 들어 24, 36의 최소공배수는 다음과 같이 구할 수 있다.

242223
362233
GCD22312
LCM2223372

마찬가지로 1~20까지의 소인수분해 결과를 가지고 가장 많이 나온 소수끼리만 곱하면 될 것이다.

이를 풀기 위해 먼저 소인수분해를 하는 클래스를 생성하였다.

#!/usr/bin/env python3

class PrimeFactorialization():
    """ to provide Factorialization """

    def __init__(self, n):
        self.__prime_list = [2,3,5,7,11,13,17,19]
        self.initial = n
        self.result = self.__get_factorialization()

    def __get_factorialization(self):
        result = []
        m = self.initial
        while True:
            for prime in self.__prime_list:
                if m < prime: break
                if m % prime == 0:
                    result.append(prime)
                    m = m // prime
                    break
            if m == 1: break

        return result

1~20까지의 최소공배수를 구하는 것이므로, 20까지의 소수를 사용하면 된다. 소수가 중요한 건 아니니까 그냥 직접 적었다. 4번문제가 소수였는데 이정도는 뭐…

#!/usr/bin/env python3
from factorialization import PrimeFactorialization

MAX_RANGE = 20
COUNT_UNDER_20 = {x: 0 for x in range(2, MAX_RANGE)}
prime_dict = {}

for i in range(2, MAX_RANGE):
    pf = PrimeFactorialization(i)
    prime_dict[i] = pf.result

for pf in prime_dict.values():
    for k in range(2, MAX_RANGE):
        if COUNT_UNDER_20[k] < pf.count(k):
            COUNT_UNDER_20[k] = pf.count(k)

r = 1
for k, v in COUNT_UNDER_20.items():
    r = r * (k**v)

print(r)

여기서 위 PrimeFactorialization클래스를 사용하여 답을 찾는다. COUNT_UNDER_20은 1~20까지의 소인수분해 결과 중, 가장 많이 나온 수를 카운팅해서 저장하는 딕셔너리다. 초기화는 딕셔너리 표현식을 사용하여 처리했다.

파이썬의 연산자 **와 //는 다음과 같다.

  • **: 지수승 구하기: 2*3=6, 2**3=2*2*2=8
  • //: 나눗셈의 결과를 floor(소수점 이하 버림)처리 - 3/2=1.5, 3//2=1