Sigh…

Project Euler problem 49~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The arithmetic sequences, made of prime terms, whose four digits are permutations of each other");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(generate_and_test_each_arithmetic_sequence_for_each_prime_number);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically for each prime n within 1k and 10k, generate and test all possible 
 16:         /// arithmetic sequence and see if they are all primes and are permutations of n
 17:         /// return the first finding!
 18:         /// </summary>
 19:         /// <returns></returns>
 20:         static long generate_and_test_each_arithmetic_sequence_for_each_prime_number()
 21:         {
 22:             var max = 10000;
 23:             var bound = (int)Math.Sqrt(max);
 24:             bool[] primes = new bool[max];
 25:             primes[0] = true;
 26:             primes[1] = true;
 27:             int s, m;
 28:             for (s = 2; s <= bound; s++)
 29:             {
 30:                 if (primes[s] == false)
 31:                 {
 32:                     for (m = s * s; m < max; m += s)
 33:                     {
 34:                         primes[m] = true;
 35:                     }
 36:                 }
 37:             }
 38:             int n1, n2, n3;
 39:             for (n1 = 1001; n1 < max; n1 += 2)
 40:             {
 41:                 if (primes[n1] == false && n1 != 1487)
 42:                 {
 43:                     bound = (max + n1) / 2;
 44:                     for (n2 = n1 + 1000; n2 < bound; n2 += 2)
 45:                     {
 46:                         if (primes[n2] == false)
 47:                         {
 48:                             n3 = n2 + (n2 - n1);
 49:                             if (n3 < max && primes[n3] == false && isPerm(n1, n2) && isPerm(n2, n3))
 50:                                 return (long)n1 * 100000000 + n2 * 10000 + n3;
 51:                         }
 52:                     }
 53:                 }
 54:             }
 55:             return 0;
 56:         }
 57: 
 58:         static bool isPerm(int original, int candidate)
 59:         {
 60:             var map = new int[11];
 61:             while (original > 0)
 62:             {
 63:                 map[original % 10]++;
 64:                 original /= 10;
 65:                 map[candidate % 10]--;
 66:                 candidate /= 10;
 67:             }
 68:             return !map.Any(n => n != 0);
 69:         }
 70: 
 71:         static Stopwatch stopwatch = new Stopwatch();
 72:         static void TestBenchSetup()
 73:         {
 74:             // Uses the second Core or Processor for the Test
 75:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 76:             // Prevents "Normal" processes from interrupting Threads
 77:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 78:             // Prevents "Normal" Threads from interrupting this thread
 79:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 80:         }
 81:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 82:         static void TestBenchLoader(Func<long> test_method)
 83:         {
 84:             stopwatch.Reset();
 85:             stopwatch.Start();
 86:             long result = 0;
 87:             long avg_tick = 0;
 88:             long avg_ms = 0;
 89:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 90:             // stabilizes the CPU cache and pipeline.
 91:             {
 92:                 result = test_method(); // Warmup
 93:             }
 94:             stopwatch.Stop();
 95:             for (int repeat = 0; repeat < 20; ++repeat)
 96:             {
 97:                 stopwatch.Reset();
 98:                 stopwatch.Start();
 99:                 result = test_method();
100:                 stopwatch.Stop();
101:                 avg_tick += stopwatch.ElapsedTicks;
102:                 avg_ms += stopwatch.ElapsedMilliseconds;
103:             }
104:             avg_tick = avg_tick / 20;
105:             avg_ms = avg_ms / 20;
106:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
107:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
108:         }
109:     }

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