Project Euler Problem 50

Problem 50

15 August 2003

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Answer: 997651

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        /// <summary>
        /// Returns primes under limit using sieve.
        /// </summary>
        /// <param name="limit">An integer to limit.</param>
        /// <returns>Primes under limit.</returns>
        static HashSet<int> primesUnder(int limit) {
            var p = new bool[limit];
            if (limit >= 3) p[2] = true;
            for (int i = 3; i < limit; i += 2) p[i] = true;
            for (int i = 3; i * i < limit; i += 2) {
                if (!p[i]) continue;
                for (int j = i + i; j < limit; j += i)
                    p[j] = false;
            }
            var r = new HashSet<int>();
            for (int i = 2; i < limit; i++)
                if (p[i]) r.Add(i);
            return r;
        }

        static void Main(string[] args) {
            const int max = 1000000;
            var primes = primesUnder(max);
            var maxCount = 0;
            var maxSum = 0;
            for (var start = 0; start < primes.Count; start++) {
                var sum = 0;
                var count = 0;
                for (var i = start; i < primes.Count; i++) {
                    var p = primes.ElementAt(i);
                    if (sum + p > max) break;
                    sum += p;
                    count++;
                    if (primes.Contains(sum) && count > maxCount) {
                        maxCount = count;
                        maxSum = sum;
                    }

                }
            }
            Console.WriteLine("{0}: {1}", maxSum, maxCount);
            Console.ReadKey();
        }
    }
}