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

Project Euler 50

Problem 50

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;
    }

    public static bool IsPrime(int n, List<int> primes) {
        foreach (int p in primes) {
            if (p * p > n) break;
            if (n % p == 0)
                return false;
        }
        return true;
    }
}

class PE050 {
    static void Main() {
        int n = 1000000;
        var primes = Prime.Sieve(n);

        int maxlen = 0;
        int ans = 0;
        for (int i = 0; i < primes.Count; i++) {
            int sum = 0;
            for (int j = i; j < primes.Count; j++) {
                sum += primes[j];
                if (sum > n) break;
                if (Prime.IsPrime(sum, primes)) {
                    if (maxlen < j - i + 1) {
                        maxlen = j - i + 1;
                        ans = sum;
                    }
                }
            }
        }

        Console.WriteLine("len:{0} prime:{1}", maxlen, ans);
    }
}