XNA 4.0!!!

Project Euler problem 12~
(still need to figured out the GCD way and need to implement the divisor function way(construct prime factor list)

Source:

  1:  class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The value of the first triangle number to have over five hundred divisors?");
  8:             sw.Start();
  9:             var sum1 = FindFactorCountTriangleNum1(500);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("linq brute force way(tick:{0} milsec:{1}): {2}"
 12:                 , sw.ElapsedTicks, sw.ElapsedMilliseconds, sum1));
 13: 
 14:             sw.Reset();
 15: 
 16:             sw.Start();
 17:             var sum2 = FindFactorCountTriangleNum2(500);
 18:             sw.Stop();
 19:             Console.WriteLine(string.Format("for loop brute force way(tick:{0} milsec:{1}): {2}"
 20:                 , sw.ElapsedTicks,sw.ElapsedMilliseconds, sum2));
 21: 
 22:             sw.Reset();
 23: 
 24:             sw.Start();
 25:             var sum3 = FactorCount();
 26:             sw.Stop();
 27:             Console.WriteLine(string.Format("smart GDC arithmetic way(tick:{0} milsec:{1}): {2}"
 28:                 , sw.ElapsedTicks, sw.ElapsedMilliseconds, sum3));
 29: 
 30:             Console.WriteLine("Press any key to exit");
 31:             Console.ReadKey();
 32:         }
 33: 
 34:         static int FindFactorCountTriangleNum1(int term)
 35:         {
 36:             var sum = 0;
 37:             var count = 0;
 38:             for (int i = 1; i < int.MaxValue; i++)
 39:             {
 40:                 sum += i;
 41: 
 42:                 count = Enumerable.Range(1, (int)Math.Sqrt(sum))
 43:                     .Where(l => sum % l == 0)
 44:                     .Select(l => sum / l != l ? 2 : 1)
 45:                     .Sum();
 46: 
 47:                 if (count > term)
 48:                     return sum;
 49:             }
 50:             return sum;
 51:         }
 52: 
 53:         static int FindFactorCountTriangleNum2(int term)
 54:         {
 55:             var sum = 0;
 56:             var count = 0;
 57:             var upper = 0;
 58:             for (int i = 1; i < int.MaxValue; i++)
 59:             {
 60:                 sum += i;
 61:                 count = 0;
 62:                 upper = (int)Math.Sqrt(sum);
 63:                 for (int j = 1; j <= upper; j++)
 64:                 {
 65:                     if (sum % j == 0)
 66:                     {
 67:                         count++;
 68:                         if (sum / j != j)
 69:                             count++;
 70:                     }
 71:                 }
 72: 
 73:                 if (count > term)
 74:                     return sum;
 75:             }
 76:             return sum;
 77:         }
 78: 
 79:         /// <summary>
 80:         /// found this on problem 12 forum, i still dont get it
 81:         /// 
 82:         /// Considering the number n*(n+1)/2
 83:         /// and let d(x) denote the number of divisors of x
 84:         /// First of all the g.c.d(n,n+1)=1
 85:         /// So if 2/n g.c.d(n/2,n+1)=1
 86:         /// and d(n*(n+1)/2)=d(n/2)*d(n+1)
 87:         /// Otherwise d(n*(n+1)/2)=d((n+1)/2)*d(n)
 88:         /// </summary>
 89:         /// <returns></returns>
 90:         static int FactorCount()
 91:         {
 92:             int limit = 500;
 93:             int cnt = 0;
 94:             for (int i = 1; cnt <= limit; i++)
 95:             {
 96:                 if (i % 2 == 0) 
 97:                     cnt = count(i / 2) * count(i + 1);
 98:                 else 
 99:                     cnt = count(i) * count((i + 1) / 2);
100:                 
101:                 if (cnt > 500)
102:                     return  i*(i+1)/2;
103:             }
104:             return 0;
105:         }
106: 
107:         static int count(int n)
108:         {
109:             int result = 0;
110:             for (int i = 1; i * i <= n; i++)
111:             {
112:                 if (n % i == 0)
113:                 {
114:                     result += 2;
115:                     if (n / i == i)
116:                         result--;
117:                 }
118:             }
119:             return result;
120:         }
121:     }

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