Multithreading\ViewModel\Xaml\WPF\PowerShell\and more…

Project Euler problem 6~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The smallest number that is evenly divisible by all of the numbers from 1 to 20");
  8:             sw.Start();
  9:             var num1 = BruteForceWay2();
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("Plain loop possibilities brute force way(tick:{0}): {1}", sw.ElapsedTicks, num1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("The smallest number that is evenly divisible by all of the numbers from 1 to 20");
 16:             sw.Start();
 17:             var num2 = ArithmeticWay(20);
 18:             sw.Stop();
 19:             Console.WriteLine(string.Format("Smart Arithmetic Way(tick:{0}): {1}", sw.ElapsedTicks, num2));
 20: 
 21:             Console.WriteLine("Press any key to exit");
 22:             Console.ReadKey();
 23:         }
 24: 
 25:         static int BruteForceWay()
 26:         {
 27:             // find the product of all prime below 20
 28:             int p = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19;
 29: 
 30:             // has to be divisible by 20
 31:             p = p + p % 20;
 32: 
 33:             bool isFound = true;
 34:             while (true)
 35:             {
 36:                 isFound = true;
 37:                 for (int i = 19; i >= 11; i--)
 38:                 {
 39:                     if (p % i != 0)
 40:                     {
 41:                         isFound = false;
 42:                         break;
 43:                     }
 44:                 }
 45:                 if (isFound)
 46:                     return p;
 47: 
 48:                 p += 20;
 49:             }
 50: 
 51:             return 0;
 52:         }
 53: 
 54:         /// <summary>
 55:         /// well, since the answer has to be divisible by product of all prime below 20
 56:         /// use that number as increment basis
 57:         /// a lot less loop than BruteForceWay(), beats the ArithmeticWay as well(hm...)
 58:         /// </summary>
 59:         /// <returns></returns>
 60:         static int BruteForceWay2()
 61:         {
 62:             // find the product of all prime below 20
 63:             int p = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19;
 64: 
 65:             bool isFound = true;
 66:             for (int i = p; i <= int.MaxValue; i += p)
 67:             {
 68:                 isFound = true;
 69:                 for (int j = 20; j > 10; j--)
 70:                 {
 71:                     if (i % j != 0)
 72:                     {
 73:                         isFound = false;
 74:                         break;
 75:                     }
 76:                 }
 77:                 if (isFound)
 78:                     return i;
 79:             }
 80:             return 0;
 81:         }
 82: 
 83:         /// <summary>
 84:         /// Base on the logic below(from the question thread):
 85:         /// This does not require programming at all. Compute the prime factorization of each 
 86:         /// number from 1 to 20, and multiply the greatest power of each prime together:
 87:         /// 20 = 2^2 * 5
 88:         /// 19 = 19
 89:         /// 18 = 2 * 3^2
 90:         /// 17 = 17
 91:         /// 16 = 2^4
 92:         /// 15 = 3 * 5
 93:         /// 14 = 2 * 7
 94:         /// 13 = 13
 95:         /// 11 = 11 
 96:         /// so basically a map
 97:         /// index is the number
 98:         /// the content:
 99:         /// -1 : not a prime number , skip
100:         /// anything other than -1 is prime
101:         /// the content's number represent the highest power of that prime number
102:         /// so if we times them together, then we would get the answer
103:         /// the tricky part is to find out highest power of each prime
104:         /// </summary>
105:         /// <param name="x"></param>
106:         /// <returns></returns>
107:         static int ArithmeticWay(int x)
108:         {
109:             int len = x + 1;
110:             int[] map = new int[len];
111:             map[0] = -1;
112:             map[1] = -1;
113:             int sum = 1;
114:             int power = 1;
115:             for (int i = 2; i < len; i++)
116:             {
117:                 if (map[i] != -1)
118:                 {
119:                     int start = i * i;
120: 
121:                     if (start >= x)
122:                         map[i] = 1;
123:                     else
124:                     {
125:                         power = 1;
126:                         for (int j = start; j <= x; j += i)
127:                         {
128:                             if (j > x)
129:                                 break;
130: 
131:                             map[j] = -1;
132:                             
133:                             if (j == Math.Pow(i, power + 1))
134:                             {
135:                                 power++;
136:                             }
137:                         }
138:                         map[i] = power;
139:                     }
140:                     sum = sum * (int)Math.Pow(i, map[i]);
141:                 }
142:                 
143:             }
144:             return sum;
145:         }
146:     }

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