12. Highly divisible triangular number

1. 개요

문제는 이곳에서 확인할 수 있다. 먼저 $n$번째 triangular number는 1부터 정수 $n$까지의 합으로 정의된다. 예를 들어 3번째 triangular number는 $1+2+3=6$이다. 문제의 목표는, 처음으로 500개가 넘는 제수(divisor)를 가지는 triangular number를 찾는 것이다. 문제를 풀고나니 더 좋은 방법이 있었기 때문에 이를 비교하기 위하여 각 풀이마다 시간을 잰다.

2. Ver 1.0

가장 간단한 방법은 어떤 triangular number를 그 숫자의 제곱근보다 작거나 같은 자연수로 나누어 가면서 제수의 수를 세는 것이다. 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

using System; using System.Diagnostics;   class ProjectEuler {     static void Main(string[] args)     {         Stopwatch sw = new Stopwatch();         sw.Start();                   ulong triangle_number = 0;         ulong i = 0;                   while(true)         {             i += 1;             triangle_number += i;                           double sqrt_triangle_number = Math.Sqrt(triangle_number);             int count = 0;             ulong divisor = 0;                           // triangle_number의 제곱근보다 작거나 같은 자연수에 대해서만 세면 된다.             for(divisor = 1; divisor <= sqrt_triangle_number; divisor++)             {                 if(triangle_number % divisor == 0)                 {                     count++;                 }             }             count *= 2;                           // 제곱의 경우 하나를 덜센다.             if(divisor == sqrt_triangle_number)             {                 count -= 1;             }             if(count >= 500)             {                 break;             }         }                   Console.WriteLine(triangle_number);         sw.Stop();         Console.WriteLine(sw.ElapsedMilliseconds.ToString() + "ms");     } }

답은 76576500이며 PC에서 약 500ms가 걸렸다.

3. Ver 2.0

문제를 풀고 사람들의 의견을 보니 더 좋은 방법이 있어 이를 소개한다. 

2 이상의 자연수 $N$은 $N=p_1^{n_1}\times p_2^{n_2}\times ...\times p_k^{n_k}$와 같이 표현된다. 단, $p_k$는 소수이며 $n_k$는 그 소수에 대한 제곱수이다. 예를 들어, $120=2^3\times 3\times 5$와 같다. 또한 $N$의 제수의 개수 $D(N)$은 $(n_1+1)(n_2+1)...(n_k+1)$와 같다. 예를 들어 120의 제수의 개수는 $(3+1)(1+1)(1+1)=16$이다. 

$n$번째 triangular number $t_n$은 $t_n=n(n+1)/2$와 같고 $n$과 $n+1$은 서로소이다. 따라서 $D(t_n)$은 $n$이 짝수인 경우 $D(t_n)=D(n/2)D(n+1)$, $n$이 홀수인 경우 $D(t_n)=D(n)D((n+1)/2)$이 된다. 

위의 방법을 사용하여 아래와 같은 코드를 작성한다. 중복 계산을 막기 위하여 $D(N)$을 저장하며 소수는 에라스토테네스의 체를 사용하여 찾는다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121

using System; using System.Collections.Generic; using System.Linq; using System.Diagnostics;   class ProjectEuler {     static List<int> prime_array;           static void Main(string[] args)     {         Stopwatch sw = new Stopwatch();         sw.Start();                   // 소수를 확보한다.         make_prime_array();                   int cnt = 0;         int n = 3;         Dictionary<int, int> D_set = new Dictionary<int, int>();                   while (cnt < 500)         {             // 0번째, 1번째 원소는 각각 n, n+1             List<int> temp_term = new List<int>();             List<int> idx = new List<int>();                           if (n % 2 == 0)             {                 idx.Add(n/2);                 idx.Add(n+1);             }             else             {                 idx.Add(n);                 idx.Add((n+1)/2);             }                           // 기존에 계산한 D(n)이 있다면 사용한다.             foreach(int i in idx)             {                 if(!D_set.ContainsKey(i))                 {                     D_set[i] = D(i);                 }                 temp_term.Add(D_set[i]);             }             cnt = temp_term.Aggregate(1,(k,j)=>k*j);             n += 1;         }                   Console.WriteLine(n*(n-1)/2);                   sw.Stop();         Console.WriteLine(sw.ElapsedMilliseconds.ToString()+"ms");               }           ///<summary>     /// 자연수 n을 소인수분해 후 number of divisors를 구한다.     ///</summary>     static int D(int n)     {         int i = 0;         List<int> cnt = new List<int>();                   while (n>1)         {             if (n % prime_array[i] == 0)             {                 cnt.Add(0);                 while (n % prime_array[i] == 0)                 {                     n /= prime_array[i];                     cnt[cnt.Count-1] += 1;                 }             }                           i += 1;                           // 소수의 개수가 충분하지 않다면 더 확보한다.             if( i >= prime_array.Count)             {                 make_prime_array();             }         }         return cnt.Aggregate(1,(k,j)=>k*(j+1));     }           ///<summary>     /// 에라토스테네스의 체를 이용하여 소수를 찾는다.     ///</summary>     static void make_prime_array()     {         int prime_candidate = 0;         int max_prime_candidate = 0;                   if(prime_array == null)         {             prime_array = new List<int>();             prime_array.Add(2);             prime_candidate = 3;         }         else         {             prime_candidate = prime_array[prime_array.Count-1] + 2;         }         max_prime_candidate = prime_candidate * 2;                   while(prime_candidate < max_prime_candidate)         {             prime_array.Add(prime_candidate);             prime_candidate += 2;         }                   for(int i = 3; i <= Math.Sqrt(max_prime_candidate); i+=2)         {             prime_array.RemoveAll(p=> p>i && p%i==0);         }     } }

답은 Ver 1.0과 같이 76576500이지만 Ver 1.0과 동일한 수행 환경에서 실행 시간은 20ms가 걸리지 않았다.