5. Smallest multiple

1. 개요

문제는 이곳에서 확인할 수 있다.

1부터 20까지의 최소공배수(Least Common Multiple, LCM)를 구하는 것이 목적이다.

2. Ver 1.0

먼저 1과 2의 LCM을 구한다. 그 LCM과 3과의 LCM을 구한다. 이를 20까지 반복한다.

두 수의 LCM을 구하기 위해서는 먼저 두 수를 소인수분해 해야 한다.
그리고 공통인수는 거듭제곱이 더 큰 것을 곱하고, 공통인수가 아닌 것은 모두 곱하면 된다.

예를 들어, $20=2^2{5}^1,24=2^3{3}^1$이므로 20과 24의 최소공배수는 $2^3{3}^1{5}^1=120$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

# -*- coding: utf-8 -*-   # ver 1.0   import numpy as np import utils as u import functools as ft   # n을 소인수분해한다. def factorization( n ):       p = u.Prime()     p.__find_prime__( np.floor( np.sqrt( n ) ) )           fac = {}           for p in p.prime:                   fac[p] = 0                   while n % p == 0:                       fac[p] += 1                           n /= p                   if n == 1:                       break                   if not fac[p]:                       del fac[p]               if not n == 1:               fac[n] = 1               return fac   # 소인수 분해를 이용하여 두 수의 최소공배수를 구한다. def lcm( a, b ):       fac_a = factorization( a )     fac_b = factorization( b )       for p in fac_b:               if p in fac_a:                           fac_a[p] = max(fac_a[p], fac_b[p] )                       fac_b.update( fac_a )           lcm = 1           for p in fac_b.items():                   lcm *= ( p[0] ** p[1] )               return lcm       print ft.reduce( lambda x, y: lcm( x, y ), range( 1, 21 ) )

3. Ver 2.0: 보다 간결한 방법

어떤 수 $k$가 1부터 10 사이의 모든 자연수로 나누어 떨어진다고 하자.

그렇다면 $k$의 인수는 10보다 작은 소수(2,3,5,7)로 충분하다.
왜냐하면 저 소수들로 10보다 작은 자연수 6, 8 등을 만들어 낼 수 있기 때문이다.

그렇다면 이들 소수 $p$를 각각 몇번씩 곱해야 하는지는 어떻게 알 수 있을까?
바로 $p^n<=10$을 만족하는 최대의 $n$을 찾으면 된다.
단, 10의 제곱근보다 크거나 같은 소수는 한번만 곱하면 된다.

예를 들면, $k$는 8로 나누어 떨어지므로 2는 3번 곱해져야 하고 9로도 나누어 떨어지므로 3은 두번 곱해져야 한다.
그렇게 하면 $k$는 10보다 작으면서 2 또는 3을 인수로 갖는 자연수(4,6,8,9)로도 나누어 떨어지게 된다.
그리고 7은 두번 이상 곱하게 되면 10보다 커지므로 한번만 곱하면 된다.

놀라운 아이디어이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

# ver 2.0   num = 20   p = u.Prime() p.__find_prime__( num ) # 20보다 작거나 같은 소수를 찾아둔다.   lim = np.sqrt( num )   k = 1   check = False   for p in p.prime:           n = 1           if check or p <= lim:             # p^n <= 20을 만족하는 최대의 정수 n           n = np.floor( np.log10( num ) / np.log10( p ) )           else:               check = True           k *= p ** n       print k

답은 232792560이다.