Project Euler 12

Problem 12

• 約数の個数は、4 約数の個数 - Wikipedia のように求める。
• Python の itertools.groupby が欲しい。素因数分解したあとのグループ化で使う。Enumerable.GroupBy でできるかな?

using System;
using System.IO;
using System.Collections.Generic;

public class P012 {
    static IEnumerable<int> Triangles() {
        int x = 0;
        for (int i = 1; /* none */; i++) {
            x += i;
            yield return x;
        }
    }

    static List<int> PrimeFactors(int n) {
        var xs = new List<int>();
        while (n % 2 == 0) {
            xs.Add(2);
            n /= 2;
        }

        for (int i = 3; i*i <= n; i += 2) {
            while (n % i == 0) {
                xs.Add(i);
                n /= i;
            }
        }
        if (n > 1) xs.Add(n);
        return xs;
    }

    static int NumberDivisors(int n) {
        int divisors = 1;
        int prev = 0, cnt = 0;
        foreach (int p in PrimeFactors(n)) {
            if (prev == p) {
                cnt++;
            }
            else {
                divisors *= cnt+1;
                prev = p;
                cnt = 1;
            }
        }
        divisors *= cnt+1;
        return divisors;
    }

    static void Main() {
        foreach (int t in Triangles()) {
            int divisors = NumberDivisors(t);
            if (divisors > 500) {
                Console.WriteLine(t);
                break;
            }
        }
    }
}

追記: NumberDivisors() の実装を GroupBy() を使うともっと簡単に書けた。

    static int NumberDivisors(int n) {
        int divisors = 1;
        foreach (var e in PrimeFactors(n).GroupBy(x => x)) {
            divisors *= e.Count() + 1;
        }
        return divisors;
    }