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?

和訳

三角数の数列は自然数の和で表わされ、7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。 三角数の最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
となる。

最初の7項について、その約数を列挙すると、以下のとおり。

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

これから、7番目の三角数である28は5つ以上の約数をもつことが分かる。

では、501 個以上の約数をもつ最初の三角数はいくらか。

当てにならないソースコード(C#)

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
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem12 {
        public Problem12() {
            int tri = 1;
            Console.WriteLine(this.ToString());

            Primes primes = new Primes(10000);
            for (int i = 2; ; i++) {
                int cnt = 1;
                tri += i;
                Dictionary<long, int> factor = primes.PrimeFactors(tri);
                foreach(var f in factor){
                    cnt *= (f.Value+1);
                }
                if (cnt > 500) {
                    Console.WriteLine(string.Format("//{0}番目の三角数{1}の約数の総数は{2}", i, tri, cnt));
                    Console.WriteLine("> " + tri);
                    break;
                }
            }
        }
    }
}
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
using System.Collections.Generic;
using System.Linq;

namespace ProjectEuler {
    public class Primes {
       
        private List<long> m_table = null;

        /// <summary>
        /// テーブルに存在する素数の数を取得する
        /// </summary>
        public int Count{
            get{
                if (m_table == null) {
                    return 0;
                }
                return m_table.Count;
            }
        }

        /// <summary>
        /// テーブル上の最大素数の値を取得する
        /// </summary>
        public long MaxValue {
            get {
                if (m_table == null) {
                    return 0;
                }
                return m_table.Last();
            }
        }

        /// <summary>
        /// n番目の素数の値を取得する
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public long this[int index] {
            get {
                if (index > Count) {
                    Make(index);
                }
                return m_table[index];
            }
        }

        /// <summary>
        /// 少なくともn番目までの素数テーブルを作成する
        /// </summary>
        /// <param name="n"></param>
        public Primes(int n){
            m_table = new List<long>(n);
            Make(n);
        }

        /// <summary>
        /// 少なくともn番目までの素数テーブルを作成する
        /// </summary>
        /// <param name="n"></param>
        public void Make(int n) {
            bool isPrime;
            //int index = 0;
            long number = 3;

            if (m_table.Count > 0) {
                number = m_table.Last();
                if (m_table.Count > n) {
                    return;
                }
            } else {
                m_table.Add(2);
            }

            for (;; number += 2) {
                isPrime = true;
                foreach (var m in m_table) {
                    if (number % m == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    m_table.Add(number);
                    if (m_table.Count == n) {
                        break;
                    }
                }
            }
        }

        /// <summary>
        /// 素因数分解を行う
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public Dictionary<long, int> PrimeFactors(long n) {
            Dictionary<long, int> primes = new Dictionary<long, int>();
            for (int i = 0; n > 1; ) {
                if(i+1 > Count){
                    Make(i+10);
                }
                if (n % m_table[i] == 0) {
                    n /= m_table[i];
                    if (primes.ContainsKey(m_table[i])) {
                        ++primes[m_table[i]];
                    } else {
                        primes.Add(m_table[i], 1);
                    }
                    continue;
                }
                ++i;
            }
            if (n > 1) {
                primes[n] = 1;
            }
            return primes;
        }
    }
}


簡単な素数クラスを作ってみました。できることはコメントに書いてある通りです。
これを使いまわすことで計算量を減らしています。