프로젝트 오일러 5번

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

최소 공배수를 구하는 문제다. 두 수의 최소 공배수라면 아주 쉽겠지만 

1부터 20까지의 최소 공배수를 구하라는 문제로, for문으로 모두 확인하는 과정은 너무 시간이 오래걸린다.

얼마나 오래걸리나 확인해봤다.

import time

def isit(num):
     for a in range(2,20):
          if (num%a != 0):
               return False
     return True

start_ = time.time()
n = 2

while not isit(20*n):
     n = n+1

print(20*n)

print(time.time()-start_)
     

232792560

14.997768878936768

정답은 나오지만 무려 15초가량 걸린 결과를 볼 수 있다.

어떻게 시간을 줄이는 지는 최소 공배수를 구하는 방법에 있다.

예를 들어, 10 과 12의 최소 공배수를 구하려면 우선 소인수 분해를 해야한다.

10 = 2 X 5

12 = 2^2 X 3

으로 표현되는데 주의 깊게 볼 것은 중복하는 소수다. 

중복하는 소수 중 차수가 큰 녀석만을 신경쓰고 나머지는 지워버리고 곱해주면 공배수가 나온다. 

5 X 2^2(4) X 3 = 60 

어찌보면 당연한 원리 이자 학교에서 초딩땐가 중딩땐가 배운 쉬운 개념이다.

방금 설명한 알고리즘을 착실히 구현해보았다.

import time

def prime_factor(num):
     n = 1
     dic = {}  #dictionary
     while num>1:
          n+=1
          if(num%n == 0):
               num = num/n
               if not dic.get(n):
                    dic[n] = 1
               dic[n] = dic[n]*n
               n-=1
          
     return dic
start_t = time.time()

dic = {}

ans = 1



for num in range(1,21):
     for key, val in prime_factor(num).items():
          dicOri = dic.get(key)
          if dicOri is None:
               dicOri = 0
          dic[key] = dicOri if val < dicOri else val
          
mult = 1
for val in dic.values():
     mult *= val

print(mult)
print(time.time()-start_t)


#dict 이용.

구조는 prime_factor 함수에서 소인수분해를 하고 12라면 dic[2] = 4, dic[3] = 3 과같은 형태로 dict 클래스로 반환한다.

#시행착오 

1. 처음에는 동일한 구조로 리스트를 이용해 구현했다. list.sort()를 이용해 12일 때 [2 2 3] 과 같은 리스트로 계산하려 했으나

이내 비효율적인 구조라는걸 깨달았다. [2 2 3] 다음에 [2 2 2 3]이 나오면 [2 2]를 지우고 [2 2 2]를 넣거나 [2]만 넣거나 해야 하는데 

전자는 비효율적이고 후자는 직관적이지가 않다.

2. dict 클래스를 이용하고 싶어졌다. 사실 모두 기억나는 건 아니라 여러가지 구글링 끝에 완성되었다.

놀랍게도 0.015초밖에 걸리지 않았다. 만족스러운 시간이고 dict라는 개념을 처음 이용해 푼 첫 문제니 만족스러운 결과라 할 수 있다.

프로젝트 오일러 선배님들은 어떻게 풀었는지 구경할 시간이다.

음.. 브루트 포스 코드가 대부분이었는데 흥미로운 코드를 찾았다.

from math import log,floor
import time

start_t = time.time()
ans=1
p_list=[2]
for r in range(3,21):
    ex_code=0
    for p in p_list:
        if r % p == 0:
            ex_code=1
    if ex_code==0:
        p_list.append(r)
for r in p_list:
    ans *=pow(r,floor(log(20,r)))
print(ans)
print(time.time()-start_t)

time 부분만 고쳐서 실행해봤는데 0.015초로 내 코드와 같았다.

한 눈에 이해가 안되서 천천히 읽어봤다. p_list에 append되는 기준은 ex_code==0, 

ex_code가 0이 되는 경우는 [3 ~ 20]인 r의 모든 값 나누기 p_list의 모든 값이 모두 나누어 떨어지지 않는 경우다.

p_list는 소수를 구하고 있는 것 같다.

Using logarithm base primes under 20, we can get max integer k such that (prime)k<20 Producting all, we can get the least common multiple of all natural numbers under 20

라고 작성자가 써줬다. 번역하자면..  

20이하의 소수를 분모로 하는 로그를 이용하면  (prime)k<20 인 k의 int형 최대 값을 얻을 수 있다. 계산을 모두 해보면, 20 이하 자연수들의 최소 공배수를 얻을 수 있다... 

라 한다. 요지는 log를 이용한다는 건데..... 10을 넣어봐도 답이 나온다.. 수학적 원리인 것 같은데 잘 모르겠어서

stackoverflow에 질문을 남기고 넘어가기로 했다.

다음은 좀 신박한 풀이.

import time

start_t = time.time()
number = 2520
result = None
while result is None:
    if all([True if number%i==0 else False for i in range(1, 21)]):
        result = number
    else:
        number+=2520
    

print(f'Answer is: {result}')
print(time.time() - start_t)

2520은 1~10까지 수의 최소공배수로, 문제에서 제시해준 수다. 

이사람은 이를 이용해 문제를 해결했다. 시간은 0.61초. 왜 더 오래걸릴까?

all()함수는 처음 봤는데, 논리 함수(?)로 any와 반대되는 개념이다. 한 마디로 ( ) 안이 모두 참일 때 참을 반환한다.

[ ]안의 내용은 Python의 삼항 연산자다. [ ] 안의 내용은 i가 1~20일 동안 number(2050)가 i로 나누어 떨어지면 True, 아니면 False가 저장된

다.  그리고 모두 true이면 true. 

이 코드는 알고보니 브루트 연산 + 2050이라는 값을 이용해 시간을 단축시킨거였다. 원리를 알고 쓴다면 나쁘지 않은 응용인 것 같다.

내가 쓴 방법 브루트 포스 기준으로 14초 -> 0.61초면 대단한 성과다.

..