C# - Lowest common multiple (LCM)

By , 8/15/2013
(0 ratings)
The method GetSmallestCommonMultiple returns the lowest common multiple of any number of values.

Help methods:
Pow - Calculates a power, I do not use the Math class because of working with long and ulong
GetPrimeFactors - Factorizes a number into its prime factors

Calculation steps:
Determine all prime factors of every number; filter the maximal count of every number contained; the filtered numbers are exponentiated with the count of occurences and then multiplied together; result: LCM

Hints:
Data type - I implemented this methods using long and ulong, to enable working with bigger values.
Negative values - Once negative values are handed over, they are multiplied with -1.
0 - Once a 0 is handed over, the result is 0 too.

Author: Koopakiller, translation by Michael List
Translate to VB
/// <summary>
/// Calculates the lowest common multiple of the given numbers.
/// </summary>
/// <param name="numbers">Numbers to be processed</param>
/// <returns>The lowest common multiple of the numbers.</returns>
static ulong GetSmallestCommonMultiple(params long[] numbers)
{
    if (numbers.Contains(0))
        return 0;

    ulong[][] lists = (from x in numbers
                       where x != 1 // 1 has no effects
                       select GetPrimeFactors((ulong)(x < 0 ? x * -1 : x))).ToArray(); //Determine all prime factors
    Dictionary<ulong, uint> list = new Dictionary<ulong, uint>();

    foreach (ulong[] l in lists)//Iterate over all prime factor lists
    {
        uint n = 1;
        ulong cur = 0;
        if (l.Length == 0)
            continue;// number is a 1
        foreach (ulong i in l)//Iterate over all prime factors
        {
            if (cur == i)
                ++n;
            else
            {
                if (cur != 0)
                {
                    if (list.ContainsKey(cur))//Does the list already contain this number?
                    {
                        if (list[cur] <= n)//Number is already in list and previous count smaller than actual count
                            list[cur] = n;//New allocation of count
                    }
                    else
                    {
                        list.Add(cur, n);//Add new number to list.
                    }
                }
                n = 1;
                cur = i;
            }
        }
        if (list.ContainsKey(cur))//Does list already contain this number?
        {
            if (list[cur] <= n)//Number is already in list and previous count smaller than actual count
                list[cur] = n;//New allocation of count
        }
        else
        {
            list.Add(cur, n);//Add new number to list
        }
    }
    ulong result = 1;
    foreach (KeyValuePair<ulong, uint> l in list)//Iterate over all values
        result *= Pow(l.Key, l.Value);//Exponentiate and multiply numbers
    return result;//Return value
}

/// <summary>
/// Exponentiates a value with the exponent.
/// </summary>
/// <param name="b">base</param>
/// <param name="e">exponent</param>
/// <returns>The power of the base <c>b</c> and the exponent <c>e</c>.</returns>
static ulong Pow(ulong b, uint e)
{
    ulong result = 1;
    for (uint i = 0; i < e; ++i)
        result *= b;
    return result;
}

/// <summary>
/// Returns the prime factors of a number.
/// </summary>
/// <param name="x">The number to be factorized.</param>
/// <returns>The prime factors of the number</returns>
/// <exception cref="System.ArgumentOutOfRangeException">Is thrown when x is smaller or equal 1.</exception>
static ulong[] GetPrimeFactors(ulong x)
{
    if (x <= 1)
        throw new ArgumentOutOfRangeException("x", "x >= 2");
    List<ulong> list = new List<ulong>();

    //? remove/list 2
    while ((double)x / (double)2 == (ulong)((double)x / (double)2))//remove 2
    {
        list.Add(2);
        x /= 2;
    }

    //? Check odd numbers for prime numbers and eventually remove/list
    for (ulong i = 3; i <= x && x != 1; )
    {
        if ((double)x / (double)i == (ulong)((double)x / (double)i)) // is number divisible by i?
        {
            list.Add(i); // Add to list
            x /= i; // Remove factor from number
        }
        else
        {
            i += 2; // Next odd number
        }
    }
    return list.ToArray(); // Return as array
}
Tagged with lcm, scm, primefactors, primenumber, prime, pow.

Comments

 

Log in, to comment!

Related Snippets