Its Friday~

Project Euler problem 77~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The first value as the sum of primes in over 5k different ways: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_dynamic_programming);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// using the same concept from code in problem 31. Instead of coins, we use seive to calculate primes
 16:         /// and within the loop, solve each of the optimum subset problem. lawl~ 
 17:         /// </summary>
 18:         static int using_dynamic_programming()
 19:         {
 20:             var max = 100; // arbitrary picked, it worked 🙂
 21:             var primes = new bool[max];
 22:             var map = new int[max];
 23:             int s, m, n;
 24:             for (s = 2; s < max; s++) // seive for finding primes
 25:             {
 26:                 if (primes[s] == false)
 27:                 {
 28:                     for (m = s * s; m < max; m += s)
 29:                     {
 30:                         primes[m] = true;
 31:                     }
 32:                     map[s]++;  // if the number is prime, then just itself is a way, so +1
 33:                     for (n = s; n < max; n++)
 34:                     {
 35:                         map[n] += map[n - s]; // for each new additional prime(s), add the # ways from (n-s)
 36:                     }
 37:                 }
 38:             }
 39:             for (s = 2; s < max; s++)
 40:             {
 41:                 if (map[s] > 5000)
 42:                     return s;
 43:             }
 44:             return 0;
 45:         }
 46: 
 47:         static Stopwatch stopwatch = new Stopwatch();
 48:         static void TestBenchSetup()
 49:         {
 50:             // Uses the second Core or Processor for the Test
 51:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 52:             // Prevents "Normal" processes from interrupting Threads
 53:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 54:             // Prevents "Normal" Threads from interrupting this thread
 55:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 56:         }
 57:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 58:         static void TestBenchLoader(Func<int> test_method)
 59:         {
 60:             stopwatch.Reset();
 61:             stopwatch.Start();
 62:             var result = 0;
 63:             long avg_tick = 0;
 64:             long avg_ms = 0;
 65:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 66:             // stabilizes the CPU cache and pipeline.
 67:             {
 68:                 result = test_method(); // Warmup
 69:             }
 70:             stopwatch.Stop();
 71:             for (int repeat = 0; repeat < 20; ++repeat)
 72:             {
 73:                 stopwatch.Reset();
 74:                 stopwatch.Start();
 75:                 result = test_method();
 76:                 stopwatch.Stop();
 77:                 avg_tick += stopwatch.ElapsedTicks;
 78:                 avg_ms += stopwatch.ElapsedMilliseconds;
 79:             }
 80:             avg_tick = avg_tick / 20;
 81:             avg_ms = avg_ms / 20;
 82:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 83:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 84:         }
 85:     }

c++

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