오일러 프로젝트 12번

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.

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

이 삼각수들의 약수를 구해봅시다.

 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

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.

그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

이것은 두가지 풀이가 있다. 처음꺼는 등차수열의 합을 이용한 무식한 풀이 방법이고, 다음꺼는 N = a^p*b^q*c^r 으로 소인수분해 되는 N의 약수의 개수 (p+1)(q+1)(r+1) 을 이용한 풀이 방법이다.

Sol 1) 솔루션이라기에는 비참한 코드

#include <stdio.h>

int main (void){

    

    int trisum = 0; int firstNum = 1;

    int lastNum = 0;

    int i,j;

    int count=0;    int divisor = 0;

    

    

    for(i=1;;i++){

        count++;    lastNum = i;

        trisum = (firstNum+lastNum)*count/2;

        j=1; divisor=0;

        for(j=1; j<=trisum ; j++){

            if(trisum%j == 0){

                printf("%d ", j);

                divisor++;

            }

        }

        printf("\n%d의 약수의 갯수 : %d\n",trisum,divisor );

        printf("\n");

        if(divisor == 500)

            break;

        

    }

    return 0;

}

Sol2 )

#include <stdio.h>

int count (int n){

int i, j, result =1;

for(j=0; (n&1) == 0; j++, n>>=1);

result *=(j+1);

for(i=3; n>=i ; i +=2){

for(j=0; n%i==0 ; n/=i, j++);

result *=(j+1);

}

return result;

}

int main (){

int tri, i;

for (tri=3, i=3; count(tri) <500; tri+=i++);

printf("%d", tri);

return 0;

}