today’s euler

Project Euler problem 47~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The first four consecutive integers to have four distinct primes factors:");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_test_each_number_for_match);
  9:             TestBenchLoader(using_seive_to_calculate_prime_factor_count);
 10:             TestBenchLoader(using_seive_to_calculate_prime_factor_count_with_unique_check);
 11: 
 12:             Console.WriteLine("Press any key to exit");
 13:             Console.ReadKey();
 14:         }
 15: 
 16:         /// <summary>
 17:         /// first construct a prime list up to 1k(using seive)
 18:         /// and check each number after 647 to see if it matches with criteria given by the question
 19:         /// 1. for each number, first find out all the prime factors, and add them to a hashset
 20:         /// 2. if prime factors added are not exactly 4, reset the hashset
 21:         /// 3  (start variable is used to make sure the numbers are continuous, if there is a gap between numbers, reset the hashset)
 22:         /// 4. if prime factors added are exactly 4, check the hashset count, if it is 16 return the answer
 23:         /// 5. if it is not 16, continues to next number
 24:         /// </summary>
 25:         /// <returns></returns>
 26:         static int brute_force_test_each_number_for_match()
 27:         {
 28:             var max = 1000; //randomly chose, it works 😛
 29:             var bound = (int)Math.Sqrt(max);
 30:             bool[] primes = new bool[max];
 31:             primes[0] = true;
 32:             primes[1] = true;
 33:             int s, m;
 34:             for (s = 2; s <= bound; s++)
 35:             {
 36:                 if (primes[s] == false)
 37:                 {
 38:                     for (m = s * s; m < max; m += s)
 39:                     {
 40:                         primes[m] = true;
 41:                     }
 42:                 }
 43:             }
 44:             var factor = 4;
 45:             var start = 0;
 46:             var num = 0;
 47:             var pwr = 1;
 48:             var set = new HashSet<int>();
 49:             var count = 1;
 50:             for (s = 647; s < 200000; s++)
 51:             {
 52:                 num = s;
 53:                 for (m = 2; m < max; m++)
 54:                 {
 55:                     if (primes[m] == false)
 56:                     {
 57:                         pwr = 1;
 58:                         while (num % m == 0)
 59:                         {
 60:                             pwr *= m;
 61:                             num /= m;
 62:                         }
 63:                         if (pwr != 1)
 64:                             set.Add(pwr);
 65:                         if (num <= 1)
 66:                             break;
 67:                     }
 68:                 }
 69:                 if (set.Count == factor * count && (s == start + 1 || start == 0))
 70:                 {
 71:                     if (count == factor)
 72:                         return s - 3;
 73: 
 74:                     start = s;
 75:                     count++;
 76:                 }
 77:                 else
 78:                 {
 79:                     set.Clear();
 80:                     count = 1;
 81:                     start = 0;
 82:                 }
 83:             }
 84:             return 0;
 85:         }
 86: 
 87:         /// <summary>
 88:         /// basically using seive mechanism to find out each number's prime factor count, and return the first
 89:         /// 4 sequential numbers that have exactly 4 primes factors.
 90:         /// but this method doesnt check for uniqueness of each prime factors.
 91:         /// still, it returns the correct answer(the answer happens to be the same as the first 4 sequential number
 92:         /// with 4 prime factors)
 93:         /// </summary>
 94:         /// <returns></returns>
 95:         static int using_seive_to_calculate_prime_factor_count()
 96:         {
 97:             var max = 1000;
 98:             var bound = (int)Math.Sqrt(max);
 99:             bool[] primes = new bool[max];
100:             primes[0] = true;
101:             primes[1] = true;
102:             int s, m;
103:             for (s = 2; s <= bound; s++) //construct a prime map up to 1k
104:             {
105:                 if (primes[s] == false)
106:                 {
107:                     for (m = s * s; m < max; m += s)
108:                     {
109:                         primes[m] = true;
110:                     }
111:                 }
112:             }
113:             var limit = 200000; //tried 10k and 100k, nothing came up
114:             var map = new int[limit];
115:             for (s = 2; s < max; s++) //using seive to calculate each number's prime factor count
116:             {
117:                 if (primes[s] == false)
118:                 {
119:                     for (m = s * 2; m < limit; m += s)
120:                     {
121:                         map[m]++;
122:                     }
123:                 }
124:             }
125:             for (s = 2; s < limit; s++) //find the first match and return the result
126:             {
127:                 if (map[s + 3] == 4 && map[s + 2] == 4 && map[s + 1] == 4 && map[s] == 4)
128:                     return s;
129:             }
130:             return 0;
131:         }
132: 
133:         /// <summary>
134:         /// basically same version as previous method, but check for unique prime factors
135:         /// </summary>
136:         /// <returns></returns>
137:         static int using_seive_to_calculate_prime_factor_count_with_unique_check()
138:         {
139:             var max = 1000;
140:             var bound = (int)Math.Sqrt(max);
141:             bool[] primes = new bool[max];
142:             primes[0] = true;
143:             primes[1] = true;
144:             int s, m;
145:             for (s = 2; s <= bound; s++)
146:             {
147:                 if (primes[s] == false)
148:                 {
149:                     for (m = s * s; m < max; m += s)
150:                     {
151:                         primes[m] = true;
152:                     }
153:                 }
154:             }
155:             var limit = 200000;
156:             List<int>[] map = new List<int>[limit];
157:             int num, factor;
158:             for (s = 2; s < max; s++)
159:             {
160:                 if (primes[s] == false)
161:                 {
162:                     for (m = s * 2; m < limit; m += s)
163:                     {
164:                         factor = 1;
165:                         num = m;
166:                         while (num % s == 0)
167:                         {
168:                             factor *= s;
169:                             num /= s;
170:                         }
171: 
172:                         if (map[m] == null)
173:                             map[m] = new List<int>();
174:                         map[m].Add(factor);
175:                     }
176:                 }
177:             }
178:             var set = new HashSet<int>();
179:             for (s = 2; s < limit; s++)
180:             {
181:                 if (map[s + 3] != null && map[s + 3].Count == 4 & map[s + 2] != null && map[s + 2].Count == 4
182:                     && map[s + 1] != null && map[s + 1].Count == 4 && map[s] != null && map[s].Count == 4)
183:                 {
184:                     set.Clear();
185:                     map.Skip(s)
186:                         .Take(4)
187:                         .SelectMany(l => l) //flatten the nested array
188:                         .ToList()
189:                         .ForEach(l => set.Add(l));
190:                     if (set.Count == 16)
191:                         return s;
192:                 }
193:             }
194:             return 0;
195:         }
196: 
197:         static Stopwatch stopwatch = new Stopwatch();
198:         static void TestBenchSetup()
199:         {
200:             // Uses the second Core or Processor for the Test
201:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
202:             // Prevents "Normal" processes from interrupting Threads
203:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
204:             // Prevents "Normal" Threads from interrupting this thread
205:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
206:         }
207:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
208:         static void TestBenchLoader(Func<int> test_method)
209:         {
210:             stopwatch.Reset();
211:             stopwatch.Start();
212:             var result = 0;
213:             long avg_tick = 0;
214:             long avg_ms = 0;
215:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
216:             // stabilizes the CPU cache and pipeline.
217:             {
218:                 result = test_method(); // Warmup
219:             }
220:             stopwatch.Stop();
221:             for (int repeat = 0; repeat < 20; ++repeat)
222:             {
223:                 stopwatch.Reset();
224:                 stopwatch.Start();
225:                 result = test_method();
226:                 stopwatch.Stop();
227:                 avg_tick += stopwatch.ElapsedTicks;
228:                 avg_ms += stopwatch.ElapsedMilliseconds;
229:             }
230:             avg_tick = avg_tick / 20;
231:             avg_ms = avg_ms / 20;
232:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
233:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
234:         }
235:     }

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