[프로젝트 오일러/파이썬] Smallest multiple

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 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520 이다.
그렇다면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마인가?

 

# 문제 : 최소공배수 구하기

	소인수	최소공배수
1	1	1(제외)
2	2	2
3	3	2*3
4	2^2	2^2*3
5	5	2^2*3*5
6	2*3	2^2*3*5
7	7	2^2*3*5*7
8	2^3	2^3*3*5*7
9	3^2	2^3*3^2*5*7
10	2*5	2^3*3^2*5*7 = 2520

 

# 풀이

1. 최대공약수(gcd)를 구하는 명령어가 담긴 math 모듈을 불러온다.

2. 파이썬에 없는 최소공배수를 구하는 함수 lcm(a, b)를 새로 만든다.

3. a×b = 두 수의 최소공배수 × 최대공약수라는 관계식을 이용해 lcm 함수를 정의한다.

4. 1부터 20까지 자연수의 최소공배수를 ‘ans’라는 변수로 나타내고, 1부터 시작한다.

5. ans의 초깃값이 1이므로 1은 제외하고, 2부터 20까지의 수를 i라는 변수로 나타낸다. 이때 나타내는 범위는 (시작 숫자, 마지막 숫자+1)이므로 (2, 21)이 된다.

6. ans와 i, 두 수 사이의 최소공배수를 구하는 함수를 이용해 1과 2의 최소공배수를 구하고, 그다음 1, 2의 최소공배수와 3의 최소공배수를 구하는 방식을 반복해 20까지 실행한다.

7. 1부터 20까지 자연수의 최소공배수를 출력한다.

 

import math
def lcm(a, b):
    return (a * b) // math.gcd(a, b)
num = 1
for i in range(2, 21):
    num = lcm(num, i)
print(num)  # 답: 232792560