woot~ Hurt Locker won

Project Euler problem 10~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The sum of all the primes below two million");
  8:             sw.Start();
  9:             var sum1 = PrimeNumberInRange(2000000);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("Sieve of Eratosthenes brute force way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         /// <summary>
 20:         /// so basically i use Sieve of Eratosthenes to construct list of prime
 21:         /// heh project euler sure likes prime
 22:         /// </summary>
 23:         /// <param name="n"></param>
 24:         /// <returns></returns>
 25:         static long PrimeNumberInRange(int n)
 26:         {
 27:             var upper = n;
 28:             var upperl = (int)Math.Sqrt(upper);
 29:             long sum = 0;
 30:             
 31:             bool[] map = new bool[upper];
 32:             map[0] = true;
 33:             map[1] = true;
 34: 
 35:             for (int l = 2; l < upperl; l++)
 36:             {
 37:                 if (map[l] == false)
 38:                 {
 39:                     for (long i = l * l; i < upper; i += l)
 40:                     {
 41:                         map[i] = true;
 42:                     }
 43:                 }
 44:             }
 45: 
 46:             for (int i = upper - 1; i > 0; i--)
 47:             {
 48:                 if (map[i] == false)
 49:                     sum += i;
 50:             }
 51: 
 52:             return sum;
 53:         }
 54:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s