Project Euler 41

Problem 41

• リストの要素を swap する関数は stackoverflow の以下を参考にしました。
• c# - Swap two items in List<T> - Stack Overflow

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

class PE041 {
    static void Swap<T>(List<T> ls, int a, int b) {
        T val = ls[a];
        ls[a] = ls[b];
        ls[b] = val;
    }
    
    static bool NextPermutation(List<int> xs) {
        int p = -1;
        for (int i = xs.Count-2; i >= 0; i--) {
            if (xs[i] < xs[i+1]) { // 右端からみて xs[i] < xs[i+1] となる i を見つける
                p = i;
                break;
            }
        }
        if (p == -1) return false;

        // i > p かつ xs[p] より大きい値のうち小さなものを探す
        int x = int.MaxValue;
        int idx = -1;
        for (int i = p+1; i < xs.Count; i++) {
            if (xs[p] < xs[i] && x > xs[i]) {
                idx = i;
                x = xs[i];
            }
        }

        Swap(xs, p, idx);

        int beg = p+1;
        int end = xs.Count-1;
        while (beg < end) {
            Swap(xs, beg, end);
            beg++;
            end--;
        }
        return true;
    }
    
    static bool IsPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        for (int i = 3; i*i <= n; i += 2) {
            if (n % i == 0) return false;
        }

        return true;
    }

    static int Calc(int n) { // n:桁数
        int ans = 0;
        List<int> digits = Enumerable.Range(1, n).ToList();
        do {
            int x = digits.Aggregate((a, b) => 10*a + b);
            if (IsPrime(x)) {
                ans = x;
            }
        } while (NextPermutation(digits));
        return ans;
    }
    
    static void Main() {
        int ans = Enumerable.Range(1, 9).Select(Calc).Max();
        Console.WriteLine(ans);
    }
}