[Project Euler] Problem 12

원문: Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?

삼각수의 수열은 자연수들의 합으로 만들 수 있다. 즉, 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 이다. 처음부터 10개의 항을 나열하면

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

처음부터 7개의 삼각수들을 인수들을 목록으로 만들면 아래와 같다.

...

우리는 28이 5개 초과의 제수(나누는 수)를 갖는 첫번째 삼각수임을 알 수 있다.
500개 초과의 제수를 갖는 첫번째 삼각수의 값은 무엇인가?

Python

수학을 조금 적용하면 어떤 수의 인수(제수)의 개수를 알 수가 있다. 어떤 수를 소인수 분해 했을 때 나오는 수들을 곱으로 표현해주었을 때, 각 단항들의 지수+1 의 곱은 인수의 개수와 같다. 예를 들어 28 = 2^2 * 7 이고, 이들의 지수+1 의 곱은 3 * 2 이다. 따라서 28의 인수의 개수는 6개다.

>>> def factor(n) :
    if n <= 0 :
        return {}
    f = {}
    for k in [2,3,5,7,11,13,17,19,23,29,31,37,41] :
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
    while n != 1 :
        if k > n**0.5 :
            f[n] = 1
            break
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
        k += 2
    return f
>>> n = 2
>>> while True :
    if eval('*'.join(map(lambda x : str(x+1), factor(n*(n+1)/2).values()))) > 500 :
        print(n*(n+1)/2)
        break
    n += 1

접기

ps.
여기서 사용한 소인수 분해 알고리즘은 내가 작성한 것이다. : http://blog.bluekyu.me/2010/07/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%9D%B8%EC%88%98-%EB%B6%84%ED%95%B4%EB%98%90%EB%8A%94-%EC%86%8C%EC%88%98-%ED%8C%90%EB%8B%A8.html