코.알.못 홍 기자의 코딩 도전기
코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갈 예정입니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 파이썬 모두 정복할 수 있지 않을까요?
홍아름 기자와 레온하르트 오일러가 여러분을 미션의 주인공으로 모십니다!
해야 할 미션은 한 가지, 1분 안에 문제의 답을 찾기만 하면 됩니다.
단, 코딩으로만 풀어야 하죠.
수학동아 자기님들! 오일러 프로젝트 문제 한번 풀어보실래요~?
<오일러 프로젝트 12번>
삼각수는 n(n+1)/2 공식으로 구할 수 있어요.
n에 1부터 차례대로 넣으면 다음과 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
그렇다면 500개 이상의 약수를 갖는 가장 작은 삼각수는 무엇일까요?
지난 45번 문제에 이어 또 다시 삼각수가 등장했습니다. 삼각수는 말 그대로 삼각형 형태를 만드는 데 필요한 점의 개수로, 1부터 시작한 연속된 자연수의 합이기도 합니다. 이번 12번 문제에서는 삼각수의 약수 개수도 구해야 합니다.
약수는 어떤 수를 나눴을 때 나눠떨어지게 하는 자연수로, 어떤 자연수 n의 약수의 개수는 n보다 작은 자연수로 일일이 나눠보며 찾을 수 있죠. 60의 약수를 한번 찾아볼까요?
이때 1과 60, 2와 30, 3과 20, 4와 15, 5와 12, 6과 10으로 둘씩 짝지어지는 것을 알 수 있습니다. 따라서 60의 경우는 6개의 자연수만 확인해보면 약수의 개수를 찾을 수 있죠. 즉 자연수 n의 약수를 찾을 때 n보다 작은 모든 자연수 대신 √n보다 작거나 같은 자연수로만 나눠보면 약수를 찾을 수 있습니다.
이 방법을 코드로 나타내 12번 문제를 해결해보겠습니다!
파이썬 완전정복! 필수 명령어
1. 약수의 개수를 구하는 함수 만들기
어떤 자연수 n이 √n보다 작은 자연수로 나눠떨어지는지를 보고, 약수의 개수를 찾는 함수 num_factors(n)을 만들겠습니다. 변수 f를 약수의 개수, i를 n을 나눌 수라고 할 때 f와 i 초깃값은 모두 2입니다. 그리고 i를 i2이 n보다 작거나 같을 때까지 1씩 늘려가며 n을 나눠떨어지게 하는지 확인합니다.
2. num_factors(n) 함수로 답 얻기
자연수의 약수의 개수를 찾는 함수에 삼각수를 대입해 답을 찾습니다. 이때 k번째 삼각수를 구하는 식 k(k+1)/2을 이용하는데, 이 식은 1부터 k까지의 자연수를 모두 더한 값을 구하는 공식과 같습니다. 따라서 k번째 삼각수를 구할 때 매번 1부터 k까지의 수들의 합을 구할 필요 없이, k-1번째 삼각수에 k를 더하기만 하면 되죠. 코드에서는 k번째 삼각수 t가 500개보다 작은 약수의 개수를 갖는다면, 그다음 k+1번째 삼각수를 구하기 위해 t에 k+1을 더한 뒤 다시 약수의 개수를 구합니다. 이 과정을 반복해 약수가 500개 이상인 수를 찾으면 while 문에서 나와 정답을 출력합니다.
도전! 오일러 프로젝트 12번 문제 뽀개기
* 코딩 언어는 Python으로 두고 실행하세요!
#1~7 약수의 개수를 얻는 num_factors(n) 함수를 정의합니다.
#8 num_factors(n) 함수를 사용해 오일러 프로젝트 12번 문제의 답을 찾는 함수 e012()를 정의합니다.
#9 삼각수 t의 초깃값은 1이고, 첫 번째 삼각수이므로 순번을 나타내는 k의 초깃값을 1로 둡니다.
#10~11 삼각수 t의 약수의 개수가 500개보다 적다면, t에 k+1을 더해 다음 k+1번째 삼각수를 구하고, while문을 반복합니다.
#12 약수의 개수가 500개 이상이면 while문을 벗어나고, 이때의 t를 돌려줍니다.
#13 함수 e012()를 실행해 답을 얻습니다.
Bonus! 오일러 퀴즈
오일러 프로젝트 12번 문제를 위 코딩창에서 풀어보고, 다음 예제 문제에도 도전해보세요!
① 약수의 개수가 500개 이상인 가장 작은 오각수를 찾아보자.
Hint. n번째 오각수 = n(3n-1)/2
② 소인수분해를 이용해 약수의 개수를 구하는 코드를 만들어보자.
Hint. 어떤 자연수가 ap×bq×cr으로 소인수분해되면, 약수의 개수는 (p+1)(q+1)(r+1)이다.
이번 해답 코드를 이용해 12번 문제의 답을 찾으면 7~8초 정도가 걸립니다. 물론 1분 이내이긴 하지만, 프로 코딩러라면 몇 초 동안 멍하니 기다리는 것도 고역이죠! 삼각수의 성질을 이용해 더 빨리 계산할 수 있는 꿀팁을 알려드릴게요!
----------------------------------------꿀팁 구간----------------------------------------
삼각수를 구하는 식 k(k+1)/2의 식을 보면, 서로소인 두 수 k와 (k+1)의 곱으로 이뤄져있습니다. 만약 k가 짝수라면 k+1은 홀수, 반대로 k가 홀수라면 k+1은 짝수가 되죠. 어느 쪽이건 짝수인 쪽을 2로 나누면 삼각수는 서로소인 두 숫자의 곱으로 나타낼 수 있습니다.
이 서로소인 두 수를 a, b라고 할 때, 삼각수의 약수 개수는 (a의 약수 개수)×(b의 약수 개수)와 같습니다. 따라서 삼각수보다 작은 자연수로 일일이 나눌 필요 없이 삼각수를 이루는 a, b를 구해 각각의 약수 개수를 구하고 곱하면 됩니다. 이 방법을 이용한 것이 아래의 코드로, 얼마나 빨라지는지 한번 실행해보세요!
