today’s euler

Project Euler problem 35~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of circular primes below one million:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(using_sieve_to_construct_primes_and_test_each_prime_candidates);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically using Sieve of Eratosthenes(from Q7) to construct a prime list under 1mil
 16:         /// and for each prime number, test each circular number, using simple equation to rotate nubmers
 17:         /// num = (num % d[size]) * 10 + num / d[size]
 18:         /// </summary>
 19:         static int using_sieve_to_construct_primes_and_test_each_prime_candidates()
 20:         {
 21:             var max = 1000000;
 22:             var bound = (int)Math.Sqrt(max);
 23:             bool[] primes = new bool[max];
 24:             primes[0] = true;
 25:             primes[1] = true;
 26:             int s, m;
 27:             for (s = 2; s <= bound; s++)
 28:             {
 29:                 if (primes[s] == false)
 30:                 {
 31:                     for (m = s * s; m < max; m += s)
 32:                     {
 33:                         primes[m] = true;
 34:                     }
 35:                 }
 36:             }
 37: 
 38:             var d = new int[] { 0, 1, 10, 100, 1000, 10000, 100000, 1000000 };
 39:             var len = d.Length;
 40:             int size, num;
 41:             var pass = false;
 42:             var count = 0;
 43: 
 44:             for (m = 0; m < max; m++)
 45:             {
 46:                 if (primes[m] == false)
 47:                 {
 48:                     size = (int)Math.Log10(m) + 1;
 49:                     num = m;
 50:                     pass = true;
 51:                     for (s = 0; s < size; s++)
 52:                     {
 53:                         num = (num % d[size]) * 10 + num / d[size];
 54:                         if (primes[num] == true)
 55:                         {
 56:                             pass = false;
 57:                             break;
 58:                         }
 59:                     }
 60:                     if (pass)
 61:                         count++;
 62:                 }
 63:             }
 64:             return count;
 65:         }
 66: 
 67:         static Stopwatch stopwatch = new Stopwatch();
 68:         static void TestBenchSetup()
 69:         {
 70:             // Uses the second Core or Processor for the Test
 71:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 72:             // Prevents "Normal" processes from interrupting Threads
 73:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 74:             // Prevents "Normal" Threads from interrupting this thread
 75:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 76:         }
 77:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 78:         static void TestBenchLoader(Func<int> test_method)
 79:         {
 80:             stopwatch.Reset();
 81:             stopwatch.Start();
 82:             var result = 0;
 83:             long avg_tick = 0;
 84:             long avg_ms = 0;
 85:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 86:             // stabilizes the CPU cache and pipeline.
 87:             {
 88:                 result = test_method(); // Warmup
 89:             }
 90:             stopwatch.Stop();
 91:             for (int repeat = 0; repeat < 20; ++repeat)
 92:             {
 93:                 stopwatch.Reset();
 94:                 stopwatch.Start();
 95:                 result = test_method();
 96:                 stopwatch.Stop();
 97:                 avg_tick += stopwatch.ElapsedTicks;
 98:                 avg_ms += stopwatch.ElapsedMilliseconds;
 99:             }
100:             avg_tick = avg_tick / 20;
101:             avg_ms = avg_ms / 20;
102:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
103:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
104:         }
105:     }

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