C#: Finding Common Multiple and Highest Common Factor (LCM-HCF)
Overview
When performing simple arithmetic with mixed fractions, finding the Lowest Common Multiple and Highest Common Factor enables simple calculations.
For example:
**25/120 + 32/72
= (25*3)/(120*3) + (32*5)/(72*5)
= 75/360 + 160/360
= 235/360
= (235/5)/(360/5)
**= **47/72
**
To do this both numbers must be factorized, to determine the common factors of the two numbers, the LCM of the two numbers, and the factor you must multiply both denominators and numerators by so both fractions have a common denominator.
The factorize Method
The factorize Method first determines the prime factors for both numbers entered, then compares those factors for common factors. The leftmost ListBox (labeled A.) contains the unique prime factors for the leftmost number. The rightmost ListBox (labeled C.) contains the unique prime factors for the rightmost number. Those factors that are present in both user entered numbers are listed in the middle Listbox.
The prime factors are determined by recursively compiling a list of all possible divisors of a number, starting with the initial user entered number, then repeating this operation with the penultimate number in the list as the new target on each iteration until the list only contains two numbers. The second number in the list, on each iteration is always a prime factor which also when multiplied by the list's penultimate number equals the target.
private void factorize(int[] numbers, ListBox[] listBoxes, Label[] outputLabels)
{
if (numbers.First() > 9999999 || numbers.Last() > 9999999)
{
MessageBox.Show("One or both numbers too large to factorise stably", "Information", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
for (int x = 0; x <= 1; x++)
{
List<int> divisors = getDivisors(numbers[x]);
if (divisors.Count != 2)
{
List<Point> levels = new List<Point>();
levels.Add(new Point(numbers[x], 1));
do
{
divisors = getDivisors(levels.Last().X);
if (divisors.Count > 2)
{
levels.Add(new Point(divisors[divisors.Count() - 2], divisors[1]));
}
else
{
break;
}
} while (true);
List<int> factors = new List<int>();
foreach (Point p in levels)
{
if (!(p.Y == 1))
{
factors.Add(p.Y);
}
}
factors.Add(levels.Last().X);
factors.Sort();
listBoxes[x == 0 ? 0 : 2].Items.Clear();
listBoxes[x == 0 ? 0 : 2].Items.AddRange(factors.Select(i => i.ToString()).ToArray());
}
else
{
listBoxes[0].Items.Clear();
listBoxes[1].Items.Clear();
listBoxes[2].Items.Clear();
outputLabels[0].Text = "LCM =";
outputLabels[1].Text = "HCF = ";
MessageBox.Show(string.Format("{0} is a Prime Number", numbers[x]),"Information", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
}
listBoxes[1].Items.Clear();
for (int x = listBoxes[0].Items.Count - 1; x >= 0; x += -1)
{
string value = listBoxes[0].Items[x].ToString();
int index = listBoxes[2].FindStringExact(value);
if (index > -1)
{
listBoxes[1].Items.Add(value);
listBoxes[0].Items.RemoveAt(x);
listBoxes[2].Items.RemoveAt(index);
}
}
DataTable dt = new DataTable();
string productString1 = string.Join("*", listBoxes[0].Items.Cast<object>().Select(o => o.ToString()).ToArray());//.TrimEnd('*');
if (listBoxes[1].Items.Count > 0)
{
string productString2 = string.Join("*", listBoxes[1].Items.Cast<object>().Select(o => o.ToString()).ToArray());
productString1 += (listBoxes[0].Items.Count > 0 ? "*" : "") + productString2;
outputLabels[1].Text = string.Format("HCF ({0}) = {1}", productString2, dt.Compute(productString2, null));
}
else
{
outputLabels[1].Text = "HCF = ";
}
productString1 += (listBoxes[2].Items.Count > 0 ? "*" : "") + string.Join("*", listBoxes[2].Items.Cast<object>().Select(o => o.ToString()).ToArray());
outputLabels[0].Text = string.Format("LCM ({0}) = {1}", productString1, dt.Compute(productString1, null));
}
The getDivisors Function
The getDivisors Function returns a list of all possible divisor pairs sorted ASC
private List<int> getDivisors(int x)
{
return new List<int>(Enumerable.Range(1, x).Where(n => x % n == 0).ToArray());
}
Other Resources