Daily Algorithm - Day 11

Highly Divisible Triangular Number

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, \dots$

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?

500개 이상의 약수를 갖는 가장 작은 삼각수를 구하는 문제이다.

내가 생각해낸 구현 방법은 다음과 같다.

1. n의 약수가 몇개인지 출력하는 함수를 작성한다.
2. 약수가 n개 이상인 가장 작은 삼각수를 출력하는 함수를 작성한다.

바로 코드를 작성해보자.

//Python

# 약수의 개수를 구하는 함수
def count_div(n):
    divisors = set() # n이 제곱수 일 경우 중복 값이 나오니 set()을 활용.
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return len(divisors)

# 삼각수 구하기
def find_tri_div(n):
    i = 1
    tri_num = 0
    
    # if~ 를 만족해서 return 할 때까지 계속 반복
    while True:
        tri_num += i
        if count_div(tri_num) > n:
            return tri_num
        i += 1

# 500개 이상의 약수를 갖는 삼각수 찾기
result = find_tri_div(500)
print(result)

>>> 76576500

오늘은 여기까지.

-2024.12.31-