Xna/Wp7/Google/and more…

Project Euler problem 108~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The least value of n for which the number of distinct solutions exceeds one-thousand: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_prime_factorization_with_google_search);
  9: 
 10:             Console.WriteLine("press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// according to http://research.att.com/~njas/sequences/A048691
 16:         /// 1/x + 1/y = 1/n is same as tau(n^2), and tau = # of divisors of n
 17:         /// since the question asks for smallest possible number, by using the prime factorization
 18:         /// of calculating  number of divisors(http://en.wikipedia.org/wiki/Divisor)
 19:         /// (2*3*5*7*11*13)^2 = 3*3*3*3*3*3 = 729 and (2*3*5*7*11*13*17)^2 = 3*3*3*3*3*3*3 = 2187
 20:         /// so n must be somewhere in between
 21:         /// </summary>
 22:         static int using_prime_factorization_with_google_search()
 23:         {
 24:             var primes = new int[] { 2, 3, 5, 7, 11, 13, 17 };
 25:             var start = 30030l * 30030l; // 2*3*5*7*11*13
 26:             var end = 510510l * 510510l; // 2*3*5*7*11*13*17
 27:             for (long n = start; n <= end; n += start)
 28:             {
 29:                 var count = prime_factorization(n, primes);
 30:                 if (count > 2000) // since the order doesnt matter
 31:                     return (int)Math.Sqrt(n);
 32:                     
 33:             }
 34:             return 0;
 35:         }
 36: 
 37:         static int prime_factorization(long n, int[] primes)
 38:         {
 39:             var count = 1;
 40:             foreach (long p in primes)
 41:             {
 42:                 var local = 0;
 43:                 while (n % p == 0)
 44:                 {
 45:                     local++;
 46:                     n /= p;
 47:                 }
 48:                 count *= (local + 1);
 49:             }
 50:             return n == 1 ? count : -1;
 51:         }
 52: 
 53:         static Stopwatch stopwatch = new Stopwatch();
 54:         static void TestBenchSetup()
 55:         {
 56:             // Uses the second Core or Processor for the Test
 57:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 58:             // Prevents "Normal" processes from interrupting Threads
 59:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 60:             // Prevents "Normal" Threads from interrupting this thread
 61:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 62:         }
 63:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 64:         static void TestBenchLoader(Func<int> test_method)
 65:         {
 66:             stopwatch.Reset();
 67:             stopwatch.Start();
 68:             long result = 0;
 69:             long avg_tick = 0;
 70:             long avg_ms = 0;
 71:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms
 72:             // stabilizes the CPU cache and pipeline.
 73:             {
 74:                 result = test_method(); // Warmup
 75:             }
 76:             stopwatch.Stop();
 77:             for (int repeat = 0; repeat < 20; ++repeat)
 78:             {
 79:                 stopwatch.Reset();
 80:                 stopwatch.Start();
 81:                 result = test_method();
 82:                 stopwatch.Stop();
 83:                 avg_tick += stopwatch.ElapsedTicks;
 84:                 avg_ms += stopwatch.ElapsedMilliseconds;
 85:             }
 86:             avg_tick = avg_tick / 20;
 87:             avg_ms = avg_ms / 20;
 88:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
 89:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
 90:         }
 91:     }

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