psotirov

Least Majority Multiple

Dec 10th, 2012
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.70 KB | None | 0 0
  1. using System;
  2.  
  3. class LeastMajorityMultiple
  4. {
  5.     static int GCD(int a, int b) // Greatest Common Divisor - Euclidean's algorithm, based on differences
  6.     {
  7.         while (a != b)
  8.         {
  9.             if (a > b) a -= b;
  10.             else b -= a;
  11.         }
  12.         return a;
  13.     }
  14.  
  15.     static void Main()
  16.     {
  17.         int numbersCount = 5; // The quantity of numbers to lookup for LMM
  18.  
  19.         int[] numbers = new int[numbersCount];
  20.         for (int i = 0; i < 5; i++) // Loop to enter numbers
  21.         {
  22.             numbers[i] = int.Parse(Console.ReadLine()); // reads a number from the console
  23.         }
  24.  
  25.         int LMM = int.MaxValue; // Least Majority Multiple takes the greatest possible number as initial value (all others should be less)
  26.         for (int i = 0; i < numbersCount - 2; i++) // prepares all number combinations in the next three loops  
  27.             for (int j = i + 1; j < numbersCount - 1; j++)
  28.                 for (int k = j + 1; k < numbersCount; k++)
  29.                 {
  30.                     int LCM1 = numbers[i] * numbers[j] / GCD(numbers[i], numbers[j]);
  31.                     // Least Common Multiply of i-th and j-th element (LCM * GCD = i-th * j-th)
  32.  
  33.                     int LCM2 = numbers[j] * numbers[k] / GCD(numbers[j], numbers[k]);
  34.                     // Least Common Multiply of j-th and k-th element (LCM * GCD = j-th * k-th)
  35.  
  36.                     LCM1 = LCM1 * LCM2 / GCD(LCM1, LCM2);
  37.                     // Least Common Multiply of LCM(i,j) and LCM(J,k) - that gives LCM of all three numbers
  38.  
  39.  
  40.                     if (LCM1 < LMM) LMM = LCM1; // Looks for the smallest possible LCM - this should be LMM
  41.                 }
  42.  
  43.         Console.WriteLine(LMM);
  44.     }
  45. }
Advertisement
Add Comment
Please, Sign In to add comment