Its Friday~

Project Euler problem 46~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest odd composite that cannot be written:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_constructed_prime_sieve);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// basically brute force to test each odd number thats not prime under randomly
 16:         /// chose limit(10k). First construct a prime sieve from 1 to 10k,
 17:         /// and for each non-prime odd number, test if the conjecture holds by iterate 
 18:         /// all the prime below it, calculate the difference, and see if a square exist
 19:         /// return the first number that no square exist for all the primes blow it.
 20:         /// </summary>
 21:         /// <returns></returns>
 22:         static int brute_force_with_constructed_prime_sieve()
 23:         {
 24:             var max = 10000; //randomly chose, it works 😛
 25:             var bound = (int)Math.Sqrt(max);
 26:             bool[] primes = new bool[max];
 27:             primes[0] = true;
 28:             primes[1] = true;
 29:             int s, m;
 30:             for (s = 2; s <= bound; s++)
 31:             {
 32:                 if (primes[s] == false)
 33:                 {
 34:                     for (m = s * s; m < max; m += s)
 35:                     {
 36:                         primes[m] = true;
 37:                     }
 38:                 }
 39:             }
 40:             var found = false;
 41:             double test_sqrt = 0;
 42:             for (s = 3; s < max; s += 2)
 43:             {
 44:                 if (primes[s] == true)
 45:                 {
 46:                     found = false;
 47:                     for (m = s - 2; m > 3; m -= 2) //reverse == alot faster, think about it!
 48:                     {
 49:                         if (primes[m] == false)
 50:                         {
 51:                             test_sqrt = Math.Sqrt((s - m) / 2);
 52:                             if (test_sqrt == (int)test_sqrt)
 53:                             {
 54:                                 found = true;
 55:                                 break; //no need to test any further
 56:                             }
 57:                         }
 58:                     }
 59:                     if (found == false)
 60:                         return s;
 61:                 }
 62:             }
 63:             return 0;
 64:         }
 65: 
 66:         static Stopwatch stopwatch = new Stopwatch();
 67:         static void TestBenchSetup()
 68:         {
 69:             // Uses the second Core or Processor for the Test
 70:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 71:             // Prevents "Normal" processes from interrupting Threads
 72:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 73:             // Prevents "Normal" Threads from interrupting this thread
 74:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 75:         }
 76:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 77:         static void TestBenchLoader(Func<int> test_method)
 78:         {
 79:             stopwatch.Reset();
 80:             stopwatch.Start();
 81:             var result = 0;
 82:             long avg_tick = 0;
 83:             long avg_ms = 0;
 84:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 85:             // stabilizes the CPU cache and pipeline.
 86:             {
 87:                 result = test_method(); // Warmup
 88:             }
 89:             stopwatch.Stop();
 90:             for (int repeat = 0; repeat < 20; ++repeat)
 91:             {
 92:                 stopwatch.Reset();
 93:                 stopwatch.Start();
 94:                 result = test_method();
 95:                 stopwatch.Stop();
 96:                 avg_tick += stopwatch.ElapsedTicks;
 97:                 avg_ms += stopwatch.ElapsedMilliseconds;
 98:             }
 99:             avg_tick = avg_tick / 20;
100:             avg_ms = avg_ms / 20;
101:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
102:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
103:         }
104:     }

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