Script / CSS

G1sUtil.js

G1sBlogger.js

CSS

G1sNavigationList.js

Posts List


2012년 2월 21일 화요일

[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>

댓글 1개:

  1. 76576500,576
    103672800,648
    137373600,576
    147911400,576
    163723560,512
    214980480,640
    228648420,576
    231221760,640
    236215980,768
    250891200,504
    286071240,512
    313112800,576
    317532600,576
    327283320,512
    333839880,640
    335936160,540
    364486500,576
    375503310,512
    376902240,576
    391986000,640
    396506880,576
    438094800,720
    450465120,576
    468930000,600
    472612140,576
    476030940,576
    479740800,576
    495007380,576
    497243880,512
    506399400,576
    522275040,576
    536592420,576
    551136600,576
    553230216,512
    579616128,512
    597214080,512
    604667700,576
    637977060,504
    639943200,576
    656107200,504
    664829880,512
    668883600,720
    677138400,576
    699398700,576
    762041280,672
    764580960,576
    768927720,512
    780144750,512
    803824560,560
    833319900,504
    842161320,1024
    853981128,576
    862598880,576
    865300800,504
    865924920,576
    888711720,512
    908424000,672
    935865216,576
    941801700,576
    953993040,720
    958147200,576
    1018606680,768
    1032419520,672
    1044039360,896
    1049530020,576

    답글삭제