Problem 12 : Highly divisible triangular number (5%)

Description

original

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?

간략해석

삼각수들 중에 약수가 500개 이상인 가장 작은 삼각수는 얼마인가.

Idea & Algorithm

naive idea

약수의 개수를 $O(\sqrt{n})$으로 구하는 방법 또는 소인수 분해를 통해 약수의 개수를 구하면 된다.

advanced idea

100만 이하의 수중 가장 많은 약수를 가지는 수는 720720으로 240개의 약수를 가지고 있다. 또한 약수의 개수는 소인수들의 개수가 매우 중요하므로 500개의 약수를 가지기 위해서는 수가 기본적으로 커야한다.

그렇기에 어림잡아 계산해본 결과 10000번째 삼각수보다는 커야하고, 나머지는 반복문으로 쉽게 해결할 수 있다.

source code

#include <stdio.h>
#define ll long long

ll cnt_div(ll num){
    ll tot = 1;
    ll p = 2;
    ll pcnt = 0;
    while(p<=num){
        if(num%p==0){
            pcnt++;
            num/=p;
        }
        else{
            if(p>2) p += 2;
            else p++;
            tot *= pcnt+1;
            pcnt = 0;
        }
    }
    tot *= pcnt+1;
    return tot;
}

int main(){
    ll num = 50005000;
    for(ll i = 10001;;i++){
        num += i;
        if(cnt_div(num)>=500){
            printf("num : %lld\n",num);
            break;
        }
    }
}

Problem 012