[Euler] Highly divisible triangular number

python 공부를 할 때, 실제로 코딩을 하면서 공부하는 방법이 익숙해 지는데 빨라서 간단한 알고리즘을 풀기로 했다.

그래서 활용한 방법이 http://projecteuler.net에서 수학 관련 알고리즘 문제를 푸는 것이었다.

첫번째로 풀 문제는

Problem 12. Highly divisible triangular number

간단히 설명하면 아래와 같이 연속적인 숫자들의 합으로 구해진 triangle number 중에서 처음으로 소수의 개수가 500개가 넘는 수를 구하는 문제이다.

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 (연속적인 숫자의 합)

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... (triangle number)

triangle number에 대한 소수를 나열하면 아래와 같다. 이때, 소수의 수가 500개가 넘는 첫 triangle number는 무엇일까가 문제이다.

 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

python으로 구현한 알고리즘 해답이다.

def divisors_count(triangle_num):
    factors = set([1, triangle_num])
    for i in range(2, triangle_num):
        if i in factors:
            return factors
        if triangle_num % 2 != 0:
            break
        elif triangle_num % i == 0:
            factors.add(i)
            factors.add(triangle_num / i)
    return factors


def triangle_number(n):
    return sum([i for i in range(1, n + 1)])


if __name__ == "__main__":

    success = False
    j = 0
    n = 0
    while not success:
        j += 1
        n = triangle_number(j)

        if len(divisors_count(n)) > 500:
            success = True
    print(n)