프로젝트 오일러 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?

 

1부터 n까지 차례로 더해서 나오는 수의 약수의 갯수가 최초로 500개가 넘는 triangle number가 얼마인지를 찾으라는 문제입니다.

 

약수의 갯수 함수

먼저 루프를 100까지만 돌리면서, 약수의 갯수를 카운트 하는 함수를 만들어 보겠습니다.

def count_factors(num):
    loop=num**0.5
    # for square number
    if loop==int(loop):
        count=1
    else:
        count=0
    i=1
    while i<loop:
        if num%i==0:
            print(i,end=',')
            count+=2
        i+=1
    print()
    return count
    
i=1;tri_num=0
while i<100:
    tri_num = tri_num + i
    count = count_factors(tri_num)
    print("loop:",i,"tri_num",tri_num,"count",count)
    i+=1
    print()

약수의 갯수를 카운트 하는 함수는 소수를 확인하는 함수와 유사합니다. 나누어봐서 떨어질때마다 카운트를 1씩 올리면 됩니다. 제곱근을 취해서 사이즈를 줄여주면 계산량이 줄어드는 것도 같습니다.

 

서브함수가 완성됐으면, 루프를 무한으로 놓고, 카운트 갯수가 500개가 넘을때 중단하면 되겠습니다. 계산시간을 측정하기 위해서, 시간함수도 추가해줬습니다.

import time
start_time = time.time()

def count_factors(num):
    loop=num**0.5
    # for square number
    if loop==int(loop):
        count=1
    else:
        count=0
    i=1
    while i<loop:
        if num%i==0:
            count+=2
        i+=1
    return count

i=1;tri_num=0
while True:
    tri_num = tri_num + i
    count = count_factors(tri_num)
    print("loop:",i,"tri_num",tri_num,"count",count)
    if count > 500:
        break
    i+=1

print("answer:",tri_num)
print("calculation time:",time.time()-start_time)

loop: 1 tri_num 1 count 1
loop: 2 tri_num 3 count 2
loop: 3 tri_num 6 count 4
loop: 4 tri_num 10 count 4
loop: 5 tri_num 15 count 4
loop: 6 tri_num 21 count 4
loop: 7 tri_num 28 count 6
loop: 8 tri_num 36 count 9
loop: 9 tri_num 45 count 6
loop: 10 tri_num 55 count 4
loop: 11 tri_num 66 count 8
loop: 12 tri_num 78 count 8