Original

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20

和訳

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。

では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

当てにならないソースコード(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
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
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem5 {
        const int max = 20;
        public Problem5() {
            int answer = 1;
            Dictionary<int, int> result = new Dictionary<int, int>();
            Console.WriteLine(this.ToString());
            for (int i=max; i>1; i--) {
                Dictionary<int, int> primes = Primes(i);
                foreach (KeyValuePair<int, int> p in primes) {
                    if (result.ContainsKey(p.Key)) {
                        if(result[p.Key] < p.Value){
                            result[p.Key] = p.Value;
                        }
                    } else {
                        result.Add(p.Key, p.Value);
                    }
                }
            }
            foreach (KeyValuePair<int, int> pair in result) {
                for (int i = 0; i < pair.Value; i++) {
                    answer *= pair.Key;
                }
                Console.WriteLine("" + pair.Key + "=" + pair.Value);
            }
            Console.WriteLine("> " + answer);
        }

        Dictionary<int,int> Primes(int n){
            Dictionary<int, int> primes = new Dictionary<int, int>();
            for (int i = 2; n > 1; ) {
                if (n % i == 0) {
                    n /= i;
                    if (primes.ContainsKey(i)) {
                        ++primes[i];
                    } else {
                        primes.Add(i, 1);
                    }
                    continue;
                }
                ++i;
            }
            if (n > 1) {
                primes[n] = 1;
            }
            return primes;
        }
    }
}


最初のループでPrimes()を呼び、素因数分解を行い、
各因数について乗数が一番多いものだけを記録していきます。
あとは積を求めるだけ。