[프로젝트 오일러] 5번 문제 & 풀이 (1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수)

Problem 5

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

처음 아이디어

1. 이 문제는 최소공배수를 구하는 문제이다
2. 숫자 4, 6의 경우, 이 때의 최대공약수(GCD)는 2, 최소공배수(LCM)는 12이고,
   4 = GCD * 2, 6 = GCD * 3 에서 LCM = GCD * 2 * 3 = GCD * 2 X GCD * 3 / GCD 이다.
3. 이 때, 추가로 숫자 7과의 최대공배수를 구하려면, 처음부터 다시 최대공약수&최소공배수를 구할 필요 없이,
   앞서 구한 최소공배수인 12와 7 사의의 최소공배수를 구하면, 이 값이 4, 6, 7의 최소공배수가 된다.
4. 같은 논리로, 1부터 차례대로 20까지 최소공배수를 구하면 된다.

import math

LCM = 1

for i in range(1, 21):
    GCD = math.gcd(i, LCM) #최대공약수 계산
    LCM = int(i*LCM/GCD) #최소공배수 계산
    print(i, LCM)

결과 :

1 1

2 2

3 6

4 12

5 60

6 60

7 420

8 840

9 2520

10 2520

11 27720

12 27720

13 360360

14 360360

15 360360

16 720720

17 12252240

18 12252240

19 232792560

20 232792560

 

다른 아이디어

1. 실제로 숫자를 1부터 차례로 1씩 늘려가며 1부터 20까지 나눈다.
2. 제일 먼저 나오는 숫자가 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수이다.

단점 : 컴퓨터가 안좋아서 그런것도 있지만, 시간이 오래 걸린다.

num = 1

while num > 0 :
    for x in range(1,21) :
        if num % x != 0 :
            num += 1
            break

    else :
        print(num)
        num = 0

결과 :

232792560

 

걸린 시간 :

497.54279375076294초.....ㄷㄷ