Xaml/WinP7/and blah~

    Project Euler problem 21~

      1:     class Program
    
      2:     {
    
      3:         static void Main(string[] args)
    
      4:         {
    
      5:             var sw = new Stopwatch();
    
      6: 
    
      7:             Console.WriteLine("The sum of all the amicable numbers under 10000");
    
      8:             sw.Start();
    
      9:             var sum1 = test(10000);
    
     10:             sw.Stop();
    
     11:             Console.WriteLine(string.Format("construct all divisor map and then match way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
    
     12: 
    
     13:             sw.Reset();
    
     14: 
    
     15:             Console.WriteLine("Press any key to exit");
    
     16:             Console.ReadKey();
    
     17:         }
    
     18: 
    
     19:         /// <summary>
    
     20:         /// basically find out all the divisor for each number from 1 to 10000 by using 
    
     21:         /// sieve of eratosthenes way of constructing a dictionary of number as key and value is list of divisors
    
     22:         /// next step is iterate the dictionary and find out all the amicable pairs and store them in a list
    
     23:         /// sum of list is the answer!
    
     24:         /// </summary>
    
     25:         /// <param name="ceiling"></param>
    
     26:         /// <returns></returns>
    
     27:         static int test(int ceiling)
    
     28:         {
    
     29:             var map = new List<int>[ceiling + 1];
    
     30:             var div = 0;
    
     31:             int bound = (int)Math.Sqrt(ceiling);
    
     32:             for (int i = 1; i <= bound; i++)
    
     33:             {
    
     34:                 for (int j = i * i; j <= ceiling; j += i)
    
     35:                 {
    
     36:                     if (map[j] == null)
    
     37:                         map[j] = new List<int>();
    
     38: 
    
     39:                     map[j].Add(i);
    
     40:                     div = j / i;
    
     41:                     if (div < j && map[j].Any(l => l == div) == false)
    
     42:                         map[j].Add(div);
    
     43:                 }
    
     44:             }
    
     45:             var sum = 0;
    
     46:             var pairs = new List<int>();
    
     47:             for (int i = 2; i < ceiling; i++)
    
     48:             {
    
     49:                 sum = map[i].Sum();
    
     50:                 if (sum < ceiling && sum != i && map[sum].Sum() == i)
    
     51:                 {
    
     52:                     if (pairs.Contains(sum) == false)
    
     53:                         pairs.Add(sum);
    
     54:                     if (pairs.Contains(i) == false)
    
     55:                         pairs.Add(i);
    
     56:                 }
    
     57:             }
    
     58:             return pairs.Sum();
    
     59:         }
    
     60:     }

    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