読者です 読者をやめる 読者になる 読者になる

Project Euler 49

Problem 49

using System;
using System.Collections.Generic;
using System.Linq;

class Prime {
    public static List<int> Sieve(int n) {
        // n 以下の全ての素数を求める
        bool[] tab = new bool[n+1];
        for (int i = 0; i < tab.Length; i++)
            tab[i] = true;

        int m = (int)Math.Sqrt(n+1);
        for (int i = 3; i <= m; i++) {
            if (tab[i]) { // i is prime
                for (int j = i+i; j <= n; j += i) {
                    tab[j] = false;
                }
            }
        }

        var primes = new List<int>();
        primes.Add(2);
        for (int i = 3; i <= n; i += 2) {
            if (tab[i]) {
                primes.Add(i);
            }
        }
        return primes;
    }
}

class PE049 {
    static int BitCount(int n) {
        int bit = 0;
        while (n > 0) {
            n &= n - 1;
            bit++;
        }
        return bit;
    }

    static IEnumerable<int[]> Combination(int n, List<int> xs) {
        int[] ret = new int[n];
        for (int i = 0; i < (1 << xs.Count); i++) {
            if (n != BitCount(i)) continue;

            int p = 0;
            for (int j = 0; j < xs.Count; j++) {
                if ((i & (1 << j)) > 0) {
                    ret[p++] = xs[j];
                }
            }
            yield return ret;
        }
    }

    static void Main() {
        // 4 桁の素数を求める
        int n = 10000;
        var primes = Prime.Sieve(n).SkipWhile(x => x < 1000).ToList();

        // 各桁でソートしてグルーピング
        var d = new Dictionary<string, List<int>>();
        foreach (int p in primes) {
            var s = string.Join("", p.ToString().ToCharArray().OrderBy(e => e));

            if (!d.ContainsKey(s)) d[s] = new List<int>();
            d[s].Add(p);
        }

        foreach (var kv in d) {
            var group = kv.Value;
            if (group.Count >= 3) {
                // 3 つを取り出して差が等しくなるか調べる
                foreach (var xs in Combination(3, group)) {
                    if (xs[1] - xs[0] == xs[2] - xs[1]) {
                        Console.WriteLine(string.Join(",", xs));
                    }
                }
            }
        }
    }
}