Friday, April 15, 2011

Project Euler - Problem 10 - C#

http://projecteuler.net/project/resources/010_7c4950764b52402fe1d29323af4e6c6f/010_overview.pdf
//The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
//Find the sum of all the primes below two million.
static UInt64 Problem10()
{
 UInt64 sum_of_primes = 0;

 foreach (var prime in primes(2000000))
 {
  sum_of_primes += prime;
  //Console.Write(prime.ToString() + ", ");
 }

 return sum_of_primes;

 // Problem10: 142913828922
}

static IEnumerable<UInt64> primes(UInt64 limit)
{
 List<UInt64> primes_list = new List<UInt64>(); // reset with 0
 bool[] nums_list = new bool[limit]; // reset with 0

 /* Create a list of all candidates. 
  * false    - Marks an invalid candidate.
  * true     - A valid candidate.
  */
 nums_list[2] = true;
 primes_list.Add(2);
 for (UInt64 current_num = 3; current_num <= limit; current_num += 2)
 {
  nums_list[current_num] = true;
 }

 // Sieve of Eratosthenes algorithm
 for (UInt64 current_num = 3; current_num <= limit; current_num += 2)
 {
  if (nums_list[current_num] == true)
  {
   primes_list.Add(current_num);

   for (UInt64 elemenator = 2 * current_num;
    elemenator < limit;
    elemenator += current_num)
   {
    nums_list[elemenator] = false;
   }
  }
 }

 foreach (var prime in primes_list)
 {
  yield return prime;
 }
}

No comments:

Post a Comment