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\)이다.

# -*- 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보다 커지므로 한번만 곱하면 된다.

놀라운 아이디어이다.

# 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이다.