today’s euler problem~

Project Euler problem 41~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The largest n-digit pandigital prime that exists?");
  6: 
  7:             TestBenchSetup();
  8:             TestBenchLoader(brute_force_find_largest_prime_in_each_range_s_permutations);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         /// <summary>
 15:         /// using code and algorithm from question 24 to generate permutation for each
 16:         /// range of digits, from most to 4(which the question already state 2143 is a prime pandigital num)
 17:         /// saw the rule of divisibility in the question's forum stated that if the sum of digits of a number 
 18:         /// is divisible by 3, then the number is divisble by 3, which makes it a non-prime(cool, never heard of it)
 19:         /// after some research:
 20:         /// http://en.wikipedia.org/wiki/Divisibility_rule
 21:         /// http://www.apronus.com/math/threediv.htm
 22:         /// </summary>
 23:         /// <returns></returns>
 24:         static int brute_force_find_largest_prime_in_each_range_s_permutations()
 25:         {
 26:             var seeds = new int[][]{
 27:                 new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
 28:                 new int[] { 1, 2, 3, 4, 5, 6, 7, 8},
 29:                 new int[] { 1, 2, 3, 4, 5, 6, 7},
 30:                 new int[] { 1, 2, 3, 4, 5, 6},
 31:                 new int[] { 1, 2, 3, 4, 5},
 32:                 new int[] { 1, 2, 3, 4},
 33:             };
 34: 
 35:             var result = 2143; //given by the question, if no bigger prime is found;
 36:             foreach (var seed in seeds)
 37:             {
 38:                 if (seed.Sum() % 3 == 0) //saw this rule from question's forum
 39:                     continue;
 40: 
 41:                 result = find_largest_prime_within_permutations(seed);
 42:                 if (result >= 2143)
 43:                     return result;
 44:             }
 45:             return result;
 46:         }
 47: 
 48:         /// <summary>
 49:         /// basically the same code from question 24, which uses the algorithm from knuth's book
 50:         /// http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
 51:         /// </summary>
 52:         /// <param name="a">contains seed values for permutation to be generated from</param>
 53:         /// <returns></returns>
 54:         static int find_largest_prime_within_permutations(int[] a)
 55:         {
 56:             var j = 0;
 57:             var l = 0;
 58:             var tmp = 0;
 59:             var len = a.Length;
 60:             var z = 0;
 61:             var candidates = new List<int>();
 62:             while (true)
 63:             {
 64:                 //step 1. Find the largest index j such that a[j] < a[j + 1].
 65:                 for (j = len - 2; j >= 0; j--)
 66:                 {
 67:                     if (a[j] < a[j + 1])
 68:                         break;
 69:                 }
 70:                 if (j == -1)
 71:                     break; // no more permutation, since no such index exist
 72:                 //step 2. Find the largest index l such that a[j] < a[l]
 73:                 for (l = len - 1; l >= 0; l--)
 74:                 {
 75:                     if (a[j] < a[l])
 76:                         break;
 77:                 }
 78:                 //step 3. Swap a[j] with a[l].
 79:                 tmp = a[j];
 80:                 a[j] = a[l];
 81:                 a[l] = tmp;
 82:                 //step 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]
 83:                 z = len - 1;
 84:                 for (l = j + 1; l < len; l++)
 85:                 {
 86:                     if (l >= z)
 87:                         break;
 88:                     tmp = a[l];
 89:                     a[l] = a[z];
 90:                     a[z] = tmp;
 91:                     z--;
 92:                 }
 93:                 //reuse j for j=a[len-1]
 94:                 j = a[len - 1];
 95:                 if (j == 1 || j == 3 || j == 7 || j == 9)
 96:                     candidates.Add(Convert.ToInt32
 97:                         (a.Aggregate(new StringBuilder(len), (s, n) => s.Append(n)).ToString()));
 98:             }
 99:             for (j = candidates.Count - 1; j >= 0; j--)
100:             {
101:                 if (isPrime(candidates[j]))
102:                     return candidates[j];
103:             }
104:             return 0;
105:         }
106: 
107:         static bool isPrime(int n)
108:         {
109:             if (n <= 1)
110:                 return false;
111:             var limit = (int)Math.Sqrt(n) + 1;
112:             for (int i = 2; i < limit; i++)
113:             {
114:                 if (n % i == 0)
115:                     return false;
116:             }
117:             return true;
118:         }
119: 
120:         static Stopwatch stopwatch = new Stopwatch();
121:         static void TestBenchSetup()
122:         {
123:             // Uses the second Core or Processor for the Test
124:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
125:             // Prevents "Normal" processes from interrupting Threads
126:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
127:             // Prevents "Normal" Threads from interrupting this thread
128:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
129:         }
130:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
131:         static void TestBenchLoader(Func<int> test_method)
132:         {
133:             stopwatch.Reset();
134:             stopwatch.Start();
135:             var result = 0;
136:             long avg_tick = 0;
137:             long avg_ms = 0;
138:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
139:             // stabilizes the CPU cache and pipeline.
140:             {
141:                 result = test_method(); // Warmup
142:             }
143:             stopwatch.Stop();
144:             for (int repeat = 0; repeat < 20; ++repeat)
145:             {
146:                 stopwatch.Reset();
147:                 stopwatch.Start();
148:                 result = test_method();
149:                 stopwatch.Stop();
150:                 avg_tick += stopwatch.ElapsedTicks;
151:                 avg_ms += stopwatch.ElapsedMilliseconds;
152:             }
153:             avg_tick = avg_tick / 20;
154:             avg_ms = avg_ms / 20;
155:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
156:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
157:         }
158:     }

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