[Python] 5-SmallestMultiple

알고리즘은 생각하지 않고 하루에 한 문제씩 풀면서 파이썬이란 언어와 친해지려고 합니다..
혹시 보시고 잘못된 부분이나 지적하실 부분이 있으면 댓글로 남겨주세요..

[문제 링크]
http://projecteuler.net/problem=5

[문제 요약]
1에서 20으로 모두 나눠지는 가장 작은 수를 구하시오..

[풀이 리뷰]
알고보면 간단한 문젠데 이해가 안되서 고민을 좀 했습니다.
프로젝트오일러에 나온 문제들은 대부분 1분내외로 풀어야 한다고 합니다.
제가 풀려고 했던 방법은 2의 배수중 20 보다 작은 가장 큰 수, 3의 배수중 20보다 작은 가장 큰수…. + 20이하의 모든 소수로 나눠지는 수를 계산하려고 했습니다.

나름 머리를 쓴다고 쓴게 반복을 최소화해서 속도를 높여보자였는데 간단한 방법이 있었습니다.

최소공배수(Least Common Multiple)를 이용하는 방법입니다.

lcm(lcm(lcm(lcm(1,2),3),4)…., 20)
위와 같은 방법으로 하면 연산을 많이 하지 않고도 답을 구할 수 있습니다.

[소스 코드]

"""
# 5_SmallestMultipl.py
# Date: 2014. 08. 04
# Author: coozplz@gmail.com
"""
import time

sTime = time.clock()
def gcd(a,b):
   """
   최대 공약수를 구하는 함수
   :param a: 숫자 입력값 1
   :param b: 숫자 입력값 2
   :return:최대 공약수
   """
   m = max(a,b)
   n = min(a,b)
   while n != 0:
       t = m % n
       (m,n)=(n,t)
   return abs(m)


"""
# 1. 숫자 1과 숫자 2의 최소공배수를 구한다.
# 2. 1의 결과와 3의 최소공배수를 구한다.
# ....
# 이전의 결과와 20의 최소공배수를 구한다.
"""

gcdValue = 1
for j in range(1, 21):
    # 최소 공배수를 구한다
    gcdValue = int(gcdValue * j / gcd(gcdValue, j))
    i = j
print(gcdValue, "최소공배수 이용=", (time.clock() - sTime) * 100)

"""
# 단순 무식하게 반복문으로 1씩 증가하면서 모두 해본다.
"""
sTime = time.clock()
num = 1
while True:
    found = True
    for i in range(1, 21):
        if num % i != 0:
            found = False
            break
    if found:
        break
    num += 1
print(num, "반복문만 사용=", (time.clock() - sTime) * 100)

[풀이 시간]
최소공배수 이용= 0.0030000000000000512
반복문만 사용= 14033.343700000001

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s