[Project Euler] 12. 500개 이상의 약수를 갖는 가장 작은 삼각수는?

12. 500개 이상의 약수를 갖는 가장 작은 삼각수는?

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개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

Click

처음에는 일일이 하나씩 더해가며 구했으나.... 이게 비 효율적이라는 생각에 고민에 고민을 거듭해 코드는 복잡하지만 좀 더 효율적인 방법을 찾음.

우선 첫번째 방법은...

<script language="Javascript" type="text/javascript">
/** 약수의 갯수를 찾는다. **/
function countSubMultiples(n){
 //count 변수 초기화.
 var cnt = 0;
 
 /* i는 1부터 n을 나눠주며 나누어 떨어지는 수들을 찾아 cnt 변수를 증가.
  * 나누는 값과 결과값이 같을경우 1을.. 그렇지 않을 경우 2를 더해줌.
  */
 var i = 1;
 var str = ""
 while(1){
  if (i > n / i)
   return cnt;
  if (n % i == 0) {
   cnt += (i == n / i) ? 1 : 2;
   str += i + ", " +(n/i) + ", ";
  }
  i++;
 }
}

/** n값을 입력받아 약수의 수가 n보다 큰 삼각함수를 출력. **/
function p012(n){
 var i = 1;
 var tric=1;
 while(1){
  if(countSubMultiples(tric)>=n)
   break;  
  i++;
  tric += i;
 } 
 alert(tric); 
}
</script>

이렇게 하고나니 너무 비 효율적인것 같아 새로 방법을 찾던 중...
삼각 수는 결국 등차수열의 합들이므로....

F(n) = n(n+1)/2

라는 공식에서부터 고민을 시작하여 다른 방법을 찾아 내었습니다.

1. F(n) = n(n+1)/2
2. 즉. F(n)의 약수는... 1,F(n), (n 또는 n/2), ((n+1) 또는 (n+1)/2),
   그리고 (n 또는 n/2), ((n+1) 또는 (n+1)/2)의 약수들과 그 약수들의 곱.
   이 중... 1은 모든 수의 약수이므로 중복.. F(n)은 (n 또는 n/2) * ((n+1) 또는 (n+1)/2) 이므로 제외....
   그러므로 F(n)의 약수는 (n 또는 n/2), ((n+1) 또는 (n+1)/2)의 약수들의 곱
   # 이 후 (n 또는 n/2) = X, ((n+1) 또는 (n+1)/2) = Y로 표기.
3. 서로 겹치지 않는 두 숫자군 M,L에서 양쪽에서 서로 하나씩의 수를 뽑아내 만들 수 있는 수의 수는 count(M) * count(L).
4. 연속한 두 수의 서로 약수들은 겹치는 수가 없겠지?? 1을 제외한 그 어떤수가 자연수와의 곱에서 1차이나는 두 수를 만들 수 는 없으니....
5. 4에 이어서... 연속한 두 수중 짝수를 2로 나눈 수의 약수들은 2로 나누기 전 약수로 이루어졌으므로 나누지 않은 다른 수와 1외에 약수가 겹치는 일은 없을 것....
6. 1~5까지의 결론으로 F(n)의 약수들의 수 = [X의 약수의 수 - 1] * [Y의 약수의 수 - 1] + [X의 약수 수 - 1] + [Y의 약수 수 - 1] + 1
7. x * y + x + y + 1 = xy + x + y + 1 = x(y+1) + y+1 = (x+1) * (y+1)
8. 6,7번에 의해.. F(n)의 약수들의 수 = [X의 약수의 수] * [Y의 약수의 수]

• 마찬가지로 어떤 수 T의 약수의 수는.. 곱해서 T가 나오는 두 수를 구해 위 8번 공식 대입.

상당히 복잡한 유추과정...  그리고 그만큼이나 복잡한 코드입니다.

<script language="Javascript" type="text/javascript">
function p012(n)
{
    //배열 선언.
    var arr = new Array();
 
    //약수의 수 계산.
    //F(n) 약수들의 수 = [X약수 수-1] * [Y약수 수-1] + [X약수 수-1] + [Y약수 수-1] + 1
    arr[1] = 1;
    var i=1;
    while(1){
 /* arr[i+1]를 채움.
  * 구하는 방식은 곱해서 i가 되는 두 수를 찾은 후 두 수의 약수값(arr)으로 구함. */
 var t= i+1;
 arr[t] = 2;  //arr[t] 초기화. i를 나눌 수 있는 수가 없으면 2로 설정되게함.
 for(var j=2; j<=t; j++){
  if(t%j == 0){
   if ((t / j) % j == 0) {
    /* t를 나누는 두 수 (t / j), j 가 약수관계일 경우
     * t 의 약수는.. (t/j) 값에다 (t/j)의 약수 중 j의 배수가
     * 아닌 수들의 수를 더하여 구함.
     */
    var temp = t/j;
    while(temp%j==0)
     temp /= j;
    arr[t] = arr[t / j] + arr[temp];
    break;
   }
   else {
    arr[t] = arr[j] * arr[parseInt(t / j)];
    break;
   }
  }
 }
 /* x,y를 구함. 
  * i 가 짝수일때와 i 가 홀 수 일때로 구분. */
 var x,y;
 if(i%2 == 0){
  x = arr[i/2];
  y = arr[i+1];
 }
 else{
  x = arr[i];
  y = arr[(i+1)/2];
 }
 //x*y가 v값보다 크면 원하는 값을 얻었으므로 i*(i+1)/2 리턴.
 if(x*y >= n)
  return (i*(i+1)/2);
 i++;
    }
}
</script>