WPF4/VS2010/and more…

Project Euler problem 37~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of the only eleven primes that are both truncatable from left to right and right to left:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(generate_all_right_truncatable_primes_and_check_each_for_left_truncatable);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// according to http://en.wikipedia.org/wiki/Truncatable_prime, there are only 83 right-truncatable primes
 16:         /// so this method first generate all the right-truncatable primes and check each primes is also left-
 17:         /// truncatable primes(using isLeftPrime(int n) method)
 18:         /// the algorithm that generates right-truncatable primes:
 19:         ///     1. start with seed list (2,3,5,7), set the range(start=0, end=seed list.count)
 20:         ///     2. for each number in the seed list from range(start to end), append a single digit number(1~9) to the end, 
 21:         ///        add new number to the seed list if the new number is also prime.
 22:         ///        for example, 2-> 21,22,23,...,29: add 23,39 to the seed list.
 23:         ///     3. after step 2, all the new numbers generated based on the numbers in the seed list are added to the
 24:         ///        seed list. update the start index and end index. the reason for this is because we dont need
 25:         ///        to go through any number except the ones that are just been generated. so basically we only want to
 26:         ///        generate new number based on the numbers in the seed list that havent been used to generate new numbers
 27:         ///     4. go to step 2
 28:         ///     5. if after the "new prime-number generation phase" and no new primes number are found. the that mean we 
 29:         ///        reach the end.
 30:         ///     6. the main reason for this algorithm is that. take the largest right-truncatable prime
 31:         ///        73939133, each successive sub number has to be prime. e.g 7,72,739,7393,73939,739391,739391(3)
 32:         ///        so base on a tested right-truncatable prime, any new prime number generated from it are also inherently
 33:         ///        right-truncatable
 34:         /// </summary>
 35:         /// <returns></returns>
 36:         static int generate_all_right_truncatable_primes_and_check_each_for_left_truncatable()
 37:         {
 38:             var seeds = new List<int>() { 2, 3, 5, 7 };
 39:             int right, index;
 40:             var start = 0;
 41:             var end = 0;
 42:             while (true)
 43:             {
 44:                 end = seeds.Count;
 45:                 if (start == end)
 46:                     break;
 47:                 for (index = start; index < end; index++)
 48:                 {
 49:                     for (int i = 1; i < 10; i += 2) // eliminate even number
 50:                     {
 51:                         if (i == 5)
 52:                             continue;
 53:                         right = seeds[index] * 10 + i;
 54:                         if (isPrime(right))
 55:                             seeds.Add(right);
 56:                     }
 57:                 }
 58:                 start = end;
 59:             }
 60:             var result = 0;
 61:             foreach (var num in seeds)
 62:             {
 63:                 if (num > 10 && isLeftPrime(num))
 64:                     result += num;
 65:             }
 66:             return result;
 67:         }
 68: 
 69:         static bool isPrime(int n)
 70:         {
 71:             if (n <= 1)
 72:                 return false;
 73: 
 74:             var limit = (int)Math.Sqrt(n) + 1;
 75:             for (int i = 2; i < limit; i++)
 76:             {
 77:                 if (n % i == 0)
 78:                     return false;
 79:             }
 80:             return true;
 81:         }
 82: 
 83:         static bool isLeftPrime(int n)
 84:         {
 85:             var tens = n < 10 ? 10 : (int)Math.Pow(10, (int)Math.Log10(n));
 86:             var rem = n;
 87:             while (tens >=10)
 88:             {
 89:                 rem = rem % tens; //doesnt need to check n, since n is already a prime in this context
 90:                 if (isPrime(rem) == false)
 91:                     return false;
 92:                 tens /= 10;
 93:             }
 94:             return true;
 95:         }
 96: 
 97:         static Stopwatch stopwatch = new Stopwatch();
 98:         static void TestBenchSetup()
 99:         {
100:             // Uses the second Core or Processor for the Test
101:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
102:             // Prevents "Normal" processes from interrupting Threads
103:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
104:             // Prevents "Normal" Threads from interrupting this thread
105:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
106:         }
107:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
108:         static void TestBenchLoader(Func<int> test_method)
109:         {
110:             stopwatch.Reset();
111:             stopwatch.Start();
112:             var result = 0;
113:             long avg_tick = 0;
114:             long avg_ms = 0;
115:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
116:             // stabilizes the CPU cache and pipeline.
117:             {
118:                 result = test_method(); // Warmup
119:             }
120:             stopwatch.Stop();
121:             for (int repeat = 0; repeat < 20; ++repeat)
122:             {
123:                 stopwatch.Reset();
124:                 stopwatch.Start();
125:                 result = test_method();
126:                 stopwatch.Stop();
127:                 avg_tick += stopwatch.ElapsedTicks;
128:                 avg_ms += stopwatch.ElapsedMilliseconds;
129:             }
130:             avg_tick = avg_tick / 20;
131:             avg_ms = avg_ms / 20;
132:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
133:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
134:         }
135:     }

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