The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
[출처 - projecteuler.net/]
이번에는 triangle numbers에 대한 새로운 용어가 나왔습니다. 용어의 정의상 해당 위치의 숫자는 1부터 연속된 숫자로 그 위치까지의 합으로 한다고 합니다. 예는 위의 문제에 나와있습니다. 그냥 지나가면 섭하니... 만약에 10번째 triangle number를 구한다고 한다면, 1 ~ 10까지의 합이 바로 그 수입니다. 아무래도 55가 되겠지요.
자 그렇다면 본 문제로 돌아가서 divisor의 갯수에 대해서 알아보겠습니다. 이 문제의 목적은 해당 triangle number에서 1을 제외한 약수를 구해서 그의 갯수의 합이 문제에서 제시한 500개를 넘는 최초의 triangle number를 구하는 것 입니다.
느낌상 왠지 정공법으로 구하면 참으로 결과는 나오겠지만 시간이 오래걸릴거 같다는 생각이 듭니다. 이번에는 기존처럼 Basic과 Advance로 나누어서 구현해 보겠습니다.
1. Basic
우선 정공법으로 구한다면, 의외로 어렵지 않습니다. 계속 반복을 하면서 다음... 그 다음... triangle numbers를 구하고, 그 수를 가지고 divisor의 갯수를 매번 구해가는 방식입니다. 이 로직의 종료 조건은... divisor개수가 500과 같거나 넘어가는 순간입니다.
[소스 코드]
import math, time
def MakeMap():
cnt = 0
chk = 2
triangleNo = 1
while cnt < 500:
temp_cnt = 0
triangleNo += chk
for i in range(1,int(math.sqrt(triangleNo))+1):
if triangleNo % i == 0:
if triangleNo // i == i:
temp_cnt += 1
else:
temp_cnt += 2
chk += 1
cnt = temp_cnt - 1
return triangleNo
if __name__ == '__main__':
start = time.time()
res = MakeMap()
print('Result : ', res)
end = time.time()
print('Spent Time : ', end - start)그나마 약간 로직이 들어간 부분은... 항상 약수에 대해서 고려를 할때 해당 수에 대해서 전체를 loop를 수행하는 것이 아닌 sqrt( )까지만 loop를 수행하는 것 입니다. 왜냐하면, sqrt( )를 넘어서는 수는 이미 앞에서 나눈 수의 나머지에 해당하기 때문입니다.
그래서 여기에서는 triangleNo // i == i, 즉 해당 수로 나누었을 때, 그 몫이 나눈수와 동일하다면 divisor 개수에 + 1을 수행하고, 다를경우에는 +2를 수행하는 방식으로 구현합니다.
[결과]
Result : 76576500
Spent Time : 6.44599986076355흠... 결과는 나오긴 했지만, 너무 많은 시간이 소요가 됩니다. 역시나 다른 로직을 생각해 봐야 겠습니다.
2. Advance
TDB.... 며칠째 생각을 해보고 있지만 별다른 아이디어가 떠오르지 않네요...
- Ayotera Lab -
댓글