C# - Integers

By , 10/15/2006
(1 ratings)
A static class providing useful methods for integer calculations
/// <summary>
/// A static class providing useful methods for integer calculations
/// </summary>
public static class Integers
{
    /// <summary>
    /// Calculates the Greatest Common Dividor of two integer
    /// </summary>
    /// <param name="Number1">the first integer</param>
    /// <param name="Number2">the second integer</param>
    /// <returns>the Greatest Common Dividor</returns>
    public static long GetGCD(long Number1, long Number2)
    {
        long remainder = 0;
        do
        {
            remainder = Number1 % Number2;
            Number1 = Number2;
            Number2 = remainder;
        } while (remainder != 0);
        return Number1;
    }

    /// <summary>
    /// Calculates the Smallest Common Multiple
    /// </summary>
    /// <param name="Number1">the first integer</param>
    /// <param name="Number2">the first integer</param>
    /// <returns>the Smallest Common Multiple</returns>
    public static long GetSCM(long Number1, long Number2)
    {
        return (Number1 * Number2) / GetGCD(Number1, Number2);
    }

    /// <summary>
    /// Checks if an integer divides another
    /// </summary>
    /// <param name="Number1">the Divident</param>
    /// <param name="Number2">the Dividor</param>
    /// <returns>true if Number2 ist dividor of Number1, else false</returns>
    public static bool IsDivider(long Number1, long Number2)
    {
        return (Number1 % Number2) == 0;
    }

    /// <summary>
    /// test if an integer is prime
    /// </summary>
    /// <param name="Number">the integer</param>
    /// <returns>true if prime else false</returns>
    public static bool IsPrime(long Number)
    {
        bool value;
        PrimeNumberReader pnreader = new PrimeNumberReader();
        pnreader.BeginGetNextPrime();
        if (pnreader.GetNextPrime(Number - 1) == Number)
        {
            value = true;
        }
        else
        {
            value = false;
        }
        pnreader.EndGetNextPrime();
        return value;
    }

    /// <summary>
    /// Converts an integer to a string containing a roman number
    /// </summary>
    /// <param name="Number">The integer</param>
    /// <returns>The string containing the roman</returns>
    public static string ToRoman(long Number)
    {
        if (Number == 0)
        {
            return string.Empty;
        }
        if (Number >= 1000)
        {
            return "M" + ToRoman(Number - 1000);
        }
        if (Number >= 900)
        {
            return "CM" + ToRoman(Number - 900);
        }
        if (Number >= 500)
        {
            return "D" + ToRoman(Number - 500);
        }
        if (Number >= 400)
        {
            return "CD" + ToRoman(Number - 400);
        }
        if (Number >= 100)
        {
            return "C" + ToRoman(Number - 100);
        }
        if (Number >= 90)
        {
            return "XC" + ToRoman(Number - 90);
        }
        if (Number >= 50)
        {
            return "L" + ToRoman(Number - 50);
        }
        if (Number >= 40)
        {
            return "XL" + ToRoman(Number - 40);
        }
        if (Number >= 10)
        {
            return "X" + ToRoman(Number - 10);
        }
        if (Number >= 9)
        {
            return "IX" + ToRoman(Number - 9);
        }
        if (Number >= 5)
        {
            return "V" + ToRoman(Number - 5);
        }
        if (Number >= 4)
        {
            return "IV" + ToRoman(Number - 4);
        }
        if (Number >= 1)
        {
            return "I" + ToRoman(Number - 1);
        }
        return string.Empty;
    }

    /// <summary>
    /// Converts a string containing a roman number to an integer
    /// </summary>
    /// <param name="Roman">The string containing a roman number</param>
    /// <returns>The integer</returns>
    public static long FromRoman(string Roman)
    {
        if (Roman.Length == 0)
        {
            return 0;
        }
        Roman = Roman.ToUpper();
        long intern = 0;
        for (int i = 0; i < Roman.Length; i++)
        {
            int value = 0;
            switch (Roman[i])
            {
                case 'M':
                    value = +1000;
                    break;
                case 'D':
                    value = +500;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("M").IndexOf(Roman[j]) != -1)
                        {
                            value = -500;
                            break;
                        }
                    }
                    break;
                case 'C':
                    value = +100;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("MD").IndexOf(Roman[j]) != -1)
                        {
                            value = -100;
                            break;
                        }
                    }
                    break;
                case 'L':
                    value = +50;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("MDC").IndexOf(Roman[j]) != -1)
                        {
                            value = -50;
                            break;
                        }
                    }
                    break;
                case 'X':
                    value = +10;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("MDCL").IndexOf(Roman[j]) != -1)
                        {
                            value = -10;
                            break;
                        }
                    }
                    break;
                case 'V':
                    value = +5;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("MDCLX").IndexOf(Roman[j]) != -1)
                        {
                            value = -5;
                            break;
                        }
                    }
                    break;
                case 'I':
                    value = +1;
                    for (int j = i + 1; j < Roman.Length; j++)
                    {
                        if (("MDCLXV").IndexOf(Roman[j]) != -1)
                        {
                            value = -1;
                            break;
                        }
                    }
                    break;
                default:
                    throw new ArgumentException("Roman number string contains an illegal character at index " + i.ToString());
            }
            intern += Convert.ToInt64(value);
        }
        return Convert.ToInt64( intern );
    }

    /// <summary>
    /// Calculates the prime number factorization of a given integer
    /// </summary>
    /// <param name="Number">The integer to be factorized</param>
    /// <returns>A SortedDictionary where the keys are the prime factors and the corresponding values their exponent</returns>
    public static SortedDictionary<long,long> GetPrimeFactorization(long Number)
    {
        if (Number == 0)
        {
            throw new ArgumentOutOfRangeException("Number", "parameter must be greater than zero");
        }
        SortedDictionary<long, long> factors = new SortedDictionary<long, long>(); 
        if (Number == 1)
        {
            factors.Add(1, 1);
            return factors;
        }
        long MaxFactor = Convert.ToInt64(Math.Ceiling(Math.Sqrt(Number)));
        long CurrentPrime;
        PrimeNumberReader pnr = new PrimeNumberReader();
        pnr.BeginGetNextPrime();
        do
        {
            CurrentPrime = pnr.GetNextPrime();
            while ((Number % CurrentPrime) == 0)
            {
                Number /= CurrentPrime;
                if (factors.ContainsKey(CurrentPrime))
                {
                    factors[CurrentPrime]++;
                }
                else
                {
                    factors.Add(CurrentPrime, 1);
                }
            }
            if (Number == 1)
            {
                break;
            }
        }
        while (MaxFactor > CurrentPrime);
        if (Number != 1)
        {
            if (factors.ContainsKey(Number))
            {
                factors[Number]++;
            }
            else
            {
                factors.Add(Number, 1);
            }
        }
        pnr.EndGetNextPrime();
        return factors;
    }

    /// <summary>
    /// Generates a list containing all the dividers of a given integer
    /// </summary>
    /// <param name="Number">The integer</param>
    /// <returns>A List containing the dividers</returns>
    public static List<long> GetDividers(long Number)
    {
        return Integers.GetDividers(GetPrimeFactorization(Number));
    }

    /// <summary>
    /// Generates a list containing all the dividers of an integer specified by its prime factorization
    /// </summary>
    /// <param name="PrimeFactorization">The prime factorization of the integer</param>
    /// <returns>A List containing the dividers</returns>
    public static List<long> GetDividers(SortedDictionary<long,long> PrimeFactorization)
    {
        SortedDictionary<long, long> DividerMask = new SortedDictionary<long, long>();
        long DividerCount = 1;
        foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
        {
            DividerCount *= pfactor.Value + 1;
            long divMask = 1;
            foreach (KeyValuePair<long, long> dmask in DividerMask)
            {
                divMask *= PrimeFactorization[dmask.Key] + 1;
            }
            DividerMask.Add(pfactor.Key, divMask);
        }
        List<long> Dividers = new List<long>(Convert.ToInt32(DividerCount));
        for (long i = 0; i < DividerCount; i++)
        {
            long Divider = 1;
            foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
            {
                long pow = (i / DividerMask[pfactor.Key]) % (pfactor.Value + 1);
                for (long j = 1; j <= pow; j++)
                {
                    Divider *= pfactor.Key;
                }
            }
            Dividers.Add(Divider);
        }
        Dividers.Sort();
        return Dividers;
    }
}

Comments

 

Log in, to comment!