Emacs/Vector/NeuralNetworks/and more…

Project Euler problem 69~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("Thevalue of n ≤ 1,000,000 for which n/φ(n) is a maximum: ");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_sieve_to_find_prime_factors_and_calculate_eulers_function);
  9:             TestBenchLoader(smart_totient_formula_observation);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 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 = 1000000;
 32:             var bound = LIMIT / 2;
 33:             var primes = new int[LIMIT + 1];
 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 max = 0;
 54:             var n = 0;
 55:             for (s = 2; s <= LIMIT; s++) // basically loop through the whole array and calculate max
 56:             {
 57:                 t = primes[s];
 58:                 if (t != 0)
 59:                 {
 60:                     cur = s / (double)t; 
 61:                     if (max < cur)
 62:                     {
 63:                         max = cur;
 64:                         n = s;
 65:                     }
 66:                 }
 67:             }
 68:             return n;
 69:         }
 70: 
 71:         /// <summary>
 72:         /// from the problem's official answer.
 73:         /// basically the number would be the the largest number within bound(1mil) that only has prime factors
 74:         /// with power of 1, so baically 2*3*5*7*11*13*17 = 510510 (dang!)
 75:         /// </summary>
 76:         static int smart_totient_formula_observation()
 77:         {
 78:             var LIMIT = 1000000;
 79:             var num = 4;
 80:             var n = 2 * 3;
 81:             var result = 0;
 82:             while (true)
 83:             {
 84:                 if (isPrime(num))
 85:                 {
 86:                     n *= num;
 87:                     if (n <= LIMIT)
 88:                         result = n;
 89:                     else
 90:                         return result;
 91:                 }
 92:                 num++;
 93:             }
 94:         }
 95: 
 96:         static bool isPrime(int n)
 97:         {
 98:             if (n <= 1)
 99:                 return false;
100:             var limit = (int)Math.Sqrt(n) + 1;
101:             for (int i = 2; i < limit; i++)
102:             {
103:                 if (n % i == 0)
104:                     return false;
105:             }
106:             return true;
107:         }
108: 
109:         static Stopwatch stopwatch = new Stopwatch();
110:         static void TestBenchSetup()
111:         {
112:             // Uses the second Core or Processor for the Test
113:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
114:             // Prevents "Normal" processes from interrupting Threads
115:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
116:             // Prevents "Normal" Threads from interrupting this thread
117:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
118:         }
119:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
120:         static void TestBenchLoader(Func<int> test_method)
121:         {
122:             stopwatch.Reset();
123:             stopwatch.Start();
124:             var result = 0;
125:             long avg_tick = 0;
126:             long avg_ms = 0;
127:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
128:             // stabilizes the CPU cache and pipeline.
129:             {
130:                 result = test_method(); // Warmup
131:             }
132:             stopwatch.Stop();
133:             for (int repeat = 0; repeat < 20; ++repeat)
134:             {
135:                 stopwatch.Reset();
136:                 stopwatch.Start();
137:                 result = test_method();
138:                 stopwatch.Stop();
139:                 avg_tick += stopwatch.ElapsedTicks;
140:                 avg_ms += stopwatch.ElapsedMilliseconds;
141:             }
142:             avg_tick = avg_tick / 20;
143:             avg_ms = avg_ms / 20;
144:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
145:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
146:         }
147:     }

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