Pattern/Wpf/WinPhone7/UX/Game/and more…

Project Euler problem 50~(ding, ding ding~, a cube!)

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The prime, below one-million, can be written as the sum of the most consecutive primes:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(calculate_length_of_each_sequence_with_starting_point_beginning_from_first_prime);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically brute force and test each sequence starting from 2,3,5,6... to max/536
 16:         /// and find the longest sequence
 17:         /// </summary>
 18:         /// <returns></returns>
 19:         static int calculate_length_of_each_sequence_with_starting_point_beginning_from_first_prime()
 20:         {
 21:             var max = 1000000;
 22:             var primes = primeList(max);
 23:             var bound = max / 536; //if we start with 2, then the sequence count is 536, so the answer must be higher than that
 24:             var i = 1;
 25:             var longest = 0;
 26:             int sum, index, length, counter;
 27:             var result = 0;
 28:             var prime = 0;
 29:             var weight = 1;
 30:             while ((i += weight) < bound)
 31:             {
 32:                 if (i == 3)
 33:                     weight++;
 34:                 if (primes[i] == false)
 35:                 {
 36:                     sum = 0;
 37:                     index = i;
 38:                     length = 0;
 39:                     counter = 0;
 40:                     while ((sum += index) < max)
 41:                     {
 42:                         counter++;
 43:                         if (primes[sum] == false)
 44:                         {
 45:                             length = counter;
 46:                             prime = sum;
 47:                         }
 48:                         do
 49:                         {
 50:                             index += weight;
 51:                         } while (index < max && primes[index]);
 52:                     }
 53:                     if (length > longest)
 54:                     {
 55:                         longest = length;
 56:                         result = prime;
 57:                     }
 58:                 }
 59:             }
 60:             return result;
 61:         }
 62: 
 63:         static bool[] primeList(int max)
 64:         {
 65:             var bound = (int)Math.Sqrt(max);
 66:             bool[] primes = new bool[max];
 67:             primes[0] = true;
 68:             primes[1] = true;
 69:             int s, m;
 70:             for (s = 2; s <= bound; s++)
 71:             {
 72:                 if (primes[s] == false)
 73:                 {
 74:                     for (m = s * s; m < max; m += s)
 75:                     {
 76:                         primes[m] = true;
 77:                     }
 78:                 }
 79:             }
 80:             return primes;
 81:         }
 82: 
 83:         static Stopwatch stopwatch = new Stopwatch();
 84:         static void TestBenchSetup()
 85:         {
 86:             // Uses the second Core or Processor for the Test
 87:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 88:             // Prevents "Normal" processes from interrupting Threads
 89:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 90:             // Prevents "Normal" Threads from interrupting this thread
 91:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 92:         }
 93:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 94:         static void TestBenchLoader(Func<int> test_method)
 95:         {
 96:             stopwatch.Reset();
 97:             stopwatch.Start();
 98:             var result = 0;
 99:             long avg_tick = 0;
100:             long avg_ms = 0;
101:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
102:             // stabilizes the CPU cache and pipeline.
103:             {
104:                 result = test_method(); // Warmup
105:             }
106:             stopwatch.Stop();
107:             for (int repeat = 0; repeat < 20; ++repeat)
108:             {
109:                 stopwatch.Reset();
110:                 stopwatch.Start();
111:                 result = test_method();
112:                 stopwatch.Stop();
113:                 avg_tick += stopwatch.ElapsedTicks;
114:                 avg_ms += stopwatch.ElapsedMilliseconds;
115:             }
116:             avg_tick = avg_tick / 20;
117:             avg_ms = avg_ms / 20;
118:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
119:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
120:         }
121:     }

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