Project Euler. #12. Highly divisible triangular number

By | 2013/02/28

Project Euler (http://projecteuler.net/) 문제12

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?

triangle numbers의 수열은 자연수를 더함으로서 생겨난다. 그러므로 7번째 triangle number는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 이다. 처음 10개의 숫자는 :

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

처음 7개의 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

28이 5개 이상의 인수를 갖는 첫번째 triangle number임을 알 수 있다.

500개 이상의 인수를 갖는 첫번째 triangle numbers는 무엇인가?


def numOfFactors(n):
    cnt = 0
    for i in range(1, int(n**(0.5))+1):
        if n%i==0:
            cnt+=1
    return cnt

n = 1
gap = 2

while True:
    if numOfFactors(n)>250:
        break
    else:
        n+=gap
        gap+=1
print n

일단 특정 수 \sqrt{n}까지의 인수만 세어보면 n의 전체 인수의 처음 절반을 알 수 있다. 이것을 무슨 법칙이라고 하는지 (혹은 이런 법칙 이름이 있는지도) 모르지만... 어쨋든 triangle numbers의 수열에서 어떤 수 n의 \sqrt{n}이 250개 이상의 인수를 가질 때, 이 n을 찾아내면 문제가 해결된다. 아주 간단하다.

하지만 문제는 이 프로그램으로 정답을 도출해내는데 약 3초 가량의 시간이 걸린다는 것. 기다리는데 그리 긴 시간은 아니지만 계산 시간을 더 줄일 수 있을 것 같다는 생각이 들게 하기엔 충분한 시간이다.


#Developed by hkapur97 on Project Euler
def problem12(n = 150):

l = (n - 1)/2; p, n = [True] * l, 1000
for i in xrange(6):
if p[i]:
s = i + i + 3; t = (s * s - 3)/2
for j in xrange(t, l, s):
p[j] = False
p = [2] + [x + x + 3 for x in xrange(l) if p[x]]

def f(n):
m, d = n ** 0.5, {}
for i in p:
if i > m:
d.update({n: 2})
return d
if n % i == 0:
d[i] = 1
while n % i == 0: n /= i; d[i] += 1
if n == 1:
return d

def c(a, b):
d, n = {}, 1
d.update(a); d.update(b)
d[2] -= 1
for i in d:
n *= d[i]
return n

a, b = f(n), f(n + 1)
while c(a, b) < 500: a, b, n = b, f(n + 2), n + 1 return (n * (n + 1))/2 [/python] 다른 사람들의 코드 중 단 0.1초도 안되는 시간에 답을 구해내는 코드를 찾아내긴 했는데, 도통 무슨 말인지 모르겠다. 아~주 독특하게 코딩이 되어있는데... 왜 매개변수 n이 150으로 자동 초기화 되도록 해놨는지도 모르겠고... 그러고보니 hkapur97는 11번 문제에서도 내가 뽑은 깔끔한 파이썬 코드를 작성한 사람인데, 설마 아이디의 97이 97년생을 의미하는 건 아니겠지? ㄷㄷㄷ 시간이 날 때, 이 사람의 코드를 천천히 분석해봐야 겠다.