WP7/PageFlipping/MVVM/and more….

Project Euler problem 27~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The product of the coefficients, a and b:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(loop_all_possible_a_and_b_in_range);
  9:             TestBenchLoader(optimized_with_reduced_range_for_a_and_b);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         static int loop_all_possible_a_and_b_in_range()
 16:         {
 17:             //generate list of primes up(using problem 7's code)
 18:             var primes = PrimeNumberInTerm(116684);
 19: 
 20:             // variables
 21:             var a = 0;
 22:             var b = 0;
 23:             var n = 0;
 24:             var p = 0;
 25:             var max_count = 0;
 26:             var result_a = 0;
 27:             var result_b = 0;
 28: 
 29:             for (a = -999; a < 999; a++)
 30:             {
 31:                 for (b = -999; b < 999; b++)
 32:                 {
 33:                     n = 0;
 34:                     do
 35:                     {
 36:                         p = n * n + a * n + b;
 37:                         n++;
 38:                     } while (primes.Contains(p));
 39: 
 40:                     if (n > max_count)
 41:                     {
 42:                         max_count = n - 1;
 43:                         result_a = a;
 44:                         result_b = b;
 45:                     }
 46:                 }
 47:             }
 48: 
 49:             return result_a * result_b;
 50:         }
 51: 
 52:         static HashSet<int> PrimeNumberInTerm(long maxCeiling)
 53:         {
 54:             var upper = maxCeiling;
 55:             var upperl = (int)Math.Sqrt(upper);
 56:             var map = new bool[upper];
 57:             map[0] = true;
 58:             map[1] = true;
 59: 
 60:             for (int l = 2; l < upperl; l++)
 61:             {
 62:                 if (map[l] == false)
 63:                 {
 64:                     for (long i = l * l; i < upper; i += l)
 65:                     {
 66:                         map[i] = true;
 67:                     }
 68:                 }
 69:             }
 70: 
 71:             var primes = new HashSet<int>();
 72:             for (int i = 0; i < upper; i++)
 73:             {
 74:                 if (map[i] == false)
 75:                     primes.Add(i);
 76:             }
 77: 
 78:             return primes;
 79:         }
 80: 
 81:         /// <summary>
 82:         /// few things:
 83:         /// 1. for n = 0, (0)^2 + a * (0) + b has to be prime, so this make b:
 84:         ///     - b has to be prime
 85:         ///     - b has to be positive
 86:         /// 2. for n = 1, (1)^2 + a + b has to be prime, so
 87:         ///     - 1 + a + b has to be prime and >= 2
 88:         ///     - so a + b >= 1
 89:         ///     - since b has to be prime, and result has to be prime
 90:         ///     - (b + 1) is even, so a has to be odd
 91:         /// </summary>
 92:         static int optimized_with_reduced_range_for_a_and_b()
 93:         {
 94:             // using seive to construct a prime map
 95:             // however, deciding the upper has been troublesome
 96:             var upper = 20000; // turns out 20000 works fine
 97:             var upperl = (int)Math.Sqrt(upper);
 98:             var map = new bool[upper];
 99:             map[0] = true;
100:             map[1] = true;
101: 
102:             for (int l = 2; l < upperl; l++)
103:             {
104:                 if (map[l] == false)
105:                 {
106:                     for (long i = l * l; i < upper; i += l)
107:                     {
108:                         map[i] = true;
109:                     }
110:                 }
111:             }
112:             
113:             var a = 0;
114:             var b = 0;
115:             var n = 0;
116:             var p = 0;
117:             var max_count = 0;
118:             var result_a = 0;
119:             var result_b = 0;
120:             for (b = 2; b < 1000; b++)
121:             {
122:                 if (map[b] == false)
123:                 {
124:                     for (a = -b; a < 1000; a += 2)
125:                     {
126:                         if (map[a + b + 1] == true)
127:                             continue;
128: 
129:                         n = 0;
130:                         do
131:                         {
132:                             p = n * n + a * n + b;
133:                             n++;
134:                         } while (p >= 2 && p < upper && map[p] == false);
135: 
136:                         if (n > max_count)
137:                         {
138:                             max_count = n - 1;
139:                             result_a = a;
140:                             result_b = b;
141:                         }
142:                     }
143:                 }
144:             }
145:             return result_a * result_b;
146:         }
147: 
148:         static Stopwatch stopwatch = new Stopwatch();
149:         static void TestBenchSetup()
150:         {
151:             // Uses the second Core or Processor for the Test
152:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
153:             // Prevents "Normal" processes from interrupting Threads
154:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
155:             // Prevents "Normal" Threads from interrupting this thread
156:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
157:         }
158:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
159:         static void TestBenchLoader(Func<int> test_method)
160:         {
161:             stopwatch.Reset();
162:             stopwatch.Start();
163:             var result = 0;
164:             long avg_tick = 0;
165:             long avg_ms = 0;
166:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
167:             // stabilizes the CPU cache and pipeline.
168:             {
169:                 result = test_method(); // Warmup
170:             }
171:             stopwatch.Stop();
172:             for (int repeat = 0; repeat < 20; ++repeat)
173:             {
174:                 stopwatch.Reset();
175:                 stopwatch.Start();
176:                 result = test_method();
177:                 stopwatch.Stop();
178:                 avg_tick += stopwatch.ElapsedTicks;
179:                 avg_ms += stopwatch.ElapsedMilliseconds;
180:             }
181:             avg_tick = avg_tick / 20;
182:             avg_ms = avg_ms / 20;
183:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
184:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
185:         }
186:     }

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