[Project Euler] Q5. Smallest multiple

Q5 : 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 나머지 (%)가 0인 숫자 찾기 (1~20에서 소수만 조건문에 포함시키면 될 것 같다.)

- 반복문을 통한 숫자 계속 증가 (20부터), 조건문에 맞는 값 나오면 탈출

 

그 다음 아이디어

- 파이썬에 있는 math함수를 활용하여, 1~20사이에 있는 모든 수의 최소공배수를 구하면 될 것 같다는 생각.

- '두개 숫자의 최소공배수를 구하면, 그 다음 숫자를 추가하여 최소공배수를 구할때 이미 구했던 두 숫자간의 최소공배수와 추가된 숫자만 최소공배수를 구하면 된다.' (참고: https://eclipse360.tistory.com/23)

 

정리

- math 수학함수의 첫 사용

- 추가된 숫자와 기존 숫자간의 최소공배수를 구할 때, 기존에 있던 최소공배수와 추가된 숫자간의 최소공배수를 구하면 된다는 사실 (처음부터 구할 필요가 없다.)

 

코드

import math
LCM = 1
for i in range(1, 21):
    LCM = math.lcm(i,LCM)
    print(i, LCM)