Mostly XNA

Project Euler problem 70~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The value of n, 1 < n  < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_sieve_to_find_prime_factors_and_calculate_eulers_function);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// (pretty much the same code from problem 69)
 16:         /// since Sieve of Eratosthenes basically test each number by checking if it is multiple of the current
 17:         /// "known" primes, essentially prime factorization(if each tested primes are saved). By combining this with the formula
 18:         /// on computing euler's function(http://en.wikipedia.org/wiki/Totient_function). the primes array itself save each
 19:         /// successive calculated totient result as more primes are being tested.
 20:         /// e.g:
 21:         /// f(36) = (2^2 * 3^2) = 36(1 - 1/2)(1 - 1/3) = ((36/2)*(36*(2-1))((36/3)*(36*(3-1)) =12;
 22:         /// so when 2 becomes current prime factor to test:
 23:         /// when it hits n, which is 36.
 24:         /// 1. if primes[36] == 0, change it to 36
 25:         /// 2. do ((primes[36]/2)*(primes[36]*(2-1)) now primes[36]=18
 26:         /// 3. later on when 3 becomes current prime factor to test
 27:         /// 4. do ((primes[36]/3)*(primes[36]*(3-1)) now primes[36]=12 (for n=36, this is it)
 28:         /// </summary>
 29:         static int using_sieve_to_find_prime_factors_and_calculate_eulers_function()
 30:         {
 31:             var LIMIT = 10000000;
 32:             var bound = LIMIT / 2;
 33:             var primes = new int[LIMIT];
 34:             int s, m, t;
 35:             for (s = 2; s < bound; s++)
 36:             {
 37:                 if (primes[s] == 0)
 38:                 {
 39:                     for (m = s * 2; m < LIMIT; m += s) // m = s * 2 since no point to test prime number(always 1 and itself)
 40:                     {
 41:                         t = primes[m];
 42: 
 43:                         if (t == 0)
 44:                             t = m; // so this is 1st time, mark t to m(the number itself)
 45: 
 46:                         t /= s; // division first to avoid overflow
 47:                         t *= (s - 1);
 48:                         primes[m] = t;
 49:                     }
 50:                 }
 51:             }
 52:             double cur = 0;
 53:             double min = int.MaxValue;
 54:             var n = 0;
 55:             for (s = LIMIT - 1; s >= 2; s--) // since the problem asks for minimum, the number is likely to be close to LIMIT
 56:             {
 57:                 t = primes[s];
 58:                 if (t != 0)
 59:                 {
 60:                     cur = s / (double)t;
 61:                     if (min > cur && isPerm(s, t))
 62:                     {
 63:                         min = cur;
 64:                         n = s;
 65:                     }
 66:                 }
 67:             }
 68:             return n;
 69:         }
 70: 
 71:         /// <summary>
 72:         /// basically just checking if two numbers are permutation of each other
 73:         /// </summary>
 74:         static bool isPerm(int original, int candidate)
 75:         {
 76:             var map = new int[10];
 77:             while (original > 0)
 78:             {
 79:                 map[original % 10]++;
 80:                 original /= 10;
 81:                 map[candidate % 10]--;
 82:                 candidate /= 10;
 83:             }
 84:             return map.All(n => n == 0);
 85:         }
 86: 
 87:         static Stopwatch stopwatch = new Stopwatch();
 88:         static void TestBenchSetup()
 89:         {
 90:             // Uses the second Core or Processor for the Test
 91:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 92:             // Prevents "Normal" processes from interrupting Threads
 93:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 94:             // Prevents "Normal" Threads from interrupting this thread
 95:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 96:         }
 97:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 98:         static void TestBenchLoader(Func<int> test_method)
 99:         {
100:             stopwatch.Reset();
101:             stopwatch.Start();
102:             var result = 0;
103:             long avg_tick = 0;
104:             long avg_ms = 0;
105:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
106:             // stabilizes the CPU cache and pipeline.
107:             {
108:                 result = test_method(); // Warmup
109:             }
110:             stopwatch.Stop();
111:             for (int repeat = 0; repeat < 20; ++repeat)
112:             {
113:                 stopwatch.Reset();
114:                 stopwatch.Start();
115:                 result = test_method();
116:                 stopwatch.Stop();
117:                 avg_tick += stopwatch.ElapsedTicks;
118:                 avg_ms += stopwatch.ElapsedMilliseconds;
119:             }
120:             avg_tick = avg_tick / 20;
121:             avg_ms = avg_ms / 20;
122:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
123:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
124:         }
125:     }

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