d라이브러리

문제 I 1~20 사이의 모든 자연수로 나눠 떨어지는 가장 작은 수를 찾아라! 

오일러 프로젝트 5번은 최소공배수를 구하는 문제입니다. 어떻게 해결할 수 있을까요?

가장 먼저 떠오른 건 지난 1월호에 소개한 1번 문제를 해결한 방법입니다. 1부터 수를 높여가면서 1~20 사이의 자연수로 나눈 나머지가 모두 0인 수를 찾는 거죠. 매우 무식한 방법이지만, 이렇게 모든 경우를 따지는 ‘브루트 포스 알고리듬’은 만들기가 쉽고, 좀 더 효율적인 알고리듬을 만드는 아이디어를 제공합니다.

하지만 이 방법을 사용하면 계산 시간이 오래 걸리는 단점이 있죠. 사용하는 수학 개념도 한정적일 수밖에 없고요. 무엇보다 폴리매스 홈페이지에서 1번 문제에 댓글을 남겨준 독자 대부분이 코딩을 빠 삭하게 알고 있어 더 뒤처질까 두려웠습니다. 이번엔 정말 수학을 이용해서 문제를 해결해보겠노라 마 음먹었답니다.

그래서 파이썬에 최소공배수를 구하는 명령어가 있을까 책과 참고자료를 뒤져봤지만, 찾을 수 없었습니다. 재난급 문제인 걸 깨달은 순간이었죠. 파이썬에서는 최소공배수를 구하는 함수 자체를 지원하지 않습니다. 다만 최대공약수를 구하는 명령어는 있었습니다. 최대공약수 명령어로 최소공배수를 구할 수 있을까요?

두 수를 소인수분해해 나타내면 약수와 배수는 물론, 최대공약수와 최소공배수도 쉽게 구할 수 있습니 다. 특히 두 수의 최대공약수와 최소공배수 사이의 관계식을 이용하면 5번 문제를 해결할 수 있죠!

자연수 a, b가 있을 때 두 수의 최대공약수와 최소공배수의 관계는 다음과 같습니다.

a×b = 최대공약수×최소공배수

이 관계식을 코딩으로 표현해 문제를 풀어봅시다.

1. math 모듈 속 최대공약수(gcd) 함수 불러오기

두 수 a, b의 최대공약수를 구하는 함수는 gcd(a, b)입니다. 영어로 최대공약수(Greatest Common Divisor)의 앞글자를 따 gcd라고 쓰지요. 하지만 파이썬 표준 라이브러리에 이 명령어는 있지 않아서, 명령어가 포함된 모듈을 불러와야 쓸 수 있습니다. 파이썬에서 모듈을 불러오는 명령어는 ‘import’이고, gcd 함수는 math 모듈에 있으니 아래와 같이 씁니다.

이 코드를 실행하더라도 항상 모듈의 이름인 math를 gcd 앞에 붙여서 math.gcd(a, b)로 써야 합니다. 예를 들어 4와 6의 최대공약수를 구하려면 math.gcd(4, 6)으로 씁니다.

2. 최소공배수 구하는 함수 만들기

최소공배수는 영어로 Least 또는 Lowest Common Multiple로, 각 단어의 앞글자를 따 lcm이라고 씁니다. 불러온 gcd 함수를 이용해서 lcm 함수를 만들려면 새롭게 함수를 만드는 ‘def’ 명령어를 써야 합니다. 그다음 a, b의 곱을 최대공약수로 나눠 최소공배수를 구하는 lcm(a, b) 함수의 식을 ‘return’ 명령어를 써서 입력합니다

① 최대공약수를 구하는 명령어가 담긴 math 모듈을 불러옵니다.
② 파이썬에 없는 최소공배수를 구하는 함수 lcm(a, b)를 새로 만듭니다.
③ a×b = 두 수의 최소공배수 × 최대공약수라는 관계식을 이용해 lcm 함수를 정의합니다.
④ 1부터 20까지 자연수의 최소공배수를 ‘ans’라는 변수로 나타내고, 1부터 시작합니다.
⑤ ans의 초깃값이 1이므로 1은 제외하고, 2부터 20까지의 수를 i라는 변수로 나타냅니다. 이
때 나타내는 범위는 (시작 숫자, 마지막 숫자+1)이므로 (2, 21)이 됩니다.
⑥ ans와 i, 두 수 사이의 최소공배수를 구하는 함수를 이용해 1과 2의 최소공배수를 구하고,
그다음 1, 2의 최소공배수와 3의 최소공배수를 구하는 방식을 반복해 20까지 실행합니다.
⑦ 1부터 20까지 자연수의 최소공배수를 출력합니다.

사실 math 모듈과 def 명령어를 알기 전, 10번 문제에서 썼던 명령어를 응용해 만든 코드가 있긴 합니다(쭈글…). 그 기상천외한 코드가 궁금하다면 폴리매스 홈페이지에서 확인하고 도움의 손길을 내밀어주세요! 영화 ‘엑시트’의 주인공들이 보냈던 간절한 SOS 신호를 보내며 마무리합니다.
‘따따따 따-따-따- 따따따!’

※편집자 주. 코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갈 예정입니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트로, 수학 문제를 프로그래밍으로 해결하는 게 목적이지요. 홍 기자와 함께 한다면 수학과 파이썬 모두 정복할 수도…?

참고자료

박응용 ‘점프 투 파이썬’