Thursday 16 April 2009

PROJECT EULER #50

Link to Project Euler problem 50

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?



using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 50
DateTime start = DateTime.Now;
List<int> primes = GeneratePrimes(1000000);
int max = 0, total = 0, initial = 0;
for (int i = 0; i < 5; i++)
{
int sum = 0, number = 0;
for (int j = i; j < primes.Count; j++)
{
sum += primes[j];
if (sum > 1000000) break;
number++;
if (primes.Contains(sum))
if (number > total)
{
total = number;
max = sum;
initial = primes[i];
}
}
}
Console.WriteLine("{0} steps from {1} give {2}", total, initial, max);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
public static bool IsPrime(int n)
{
if (n < 2)
return false;
if (n == 2)
return true;
for (long i = 2; i <= Math.Sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
public static List<int> GeneratePrimes(int n)
{
var primes = new List<int> { 2, 3 };
for (int i = 5; i <= n; i += 2)
{
if (IsPrime(i))
primes.Add(i);
}
return primes;
}
}
}

No comments: