Prime numbers, Prime Factors and LCM

Question

I am trying to generate LCM by prime factorization. I have already done the other way around to generate LCM using GCD but I am trying to achieve it using prime factorization.

I am getting right prime factors but the problem is that to generate LCM we need to multiply each factor the greatest number of times it occurs in either number's factors. Reference

Now I don't like the code I come up with to achieve this. The logic is to retrieve factors of both numbers and then create a hash/counter for each factor. Finally multiply the factor with the result so far and the greatest number of times in each hash counter list.

I would like to request to review my all methods IsPrime, PrimeFactors, LeastCommonMultipleByPrimeFactorization etc. In particular the main LeastCommonMultipleByPrimeFactorization method. Please feel free to pass your comments and suggestions. I would be happy to see some simplest way to achieve this.

Code snippet:

    public static bool IsPrime(int n)
    {
        for (int i = 2; i <= n; i++)
        {
            if (n % i == 0)
            {
                if (i == n)
                    return true;
                else
                    return false;
            }
        }
        return false;
    }

    public static int[] PrimeFactors(int n)
    {
        var factors = new List<int>();
        for (int i = 2; i <= n; i++)
        {
            while (n % i == 0 && IsPrime(i))
            {
                factors.Add(i);
                n = n / i;
            }
        }
        return factors.ToArray();
    }

    public static int LeastCommonMultipleByPrimeFactorization(int m, int n)
    {
        //retrieve prime factors for both numbers
        int[] mFactors = PrimeFactors(m);
        int[] nFactors = PrimeFactors(n);

        //generate hash code to get counter for each factor 
        var mFactorsCountHash = CreateCounterHash(mFactors);
        var nFactorsCountHash = CreateCounterHash(nFactors);

        var primeFactors = new List<int>();
        primeFactors.AddRange(mFactors);
        primeFactors.AddRange(nFactors);

        int result = 1;

        //On each distinct factor... check either which number factors 
        foreach (int factor in primeFactors.Distinct())
        {
            int mfactorCount = 0;
            int nfactorCount = 0;
            if (mFactorsCountHash.ContainsKey(factor))
            {
                mfactorCount = mFactorsCountHash[factor];
            }

            if (nFactorsCountHash.ContainsKey(factor))
            {
                nfactorCount = nFactorsCountHash[factor];
            }

            int numberOfCount = mfactorCount > nfactorCount ? mfactorCount : nfactorCount;
            result = factor * result * numberOfCount;
        }

        return result;
    }

    private static Dictionary<int, int> CreateCounterHash(IEnumerable<int> mFactors)
    {
        Dictionary<int, int> hash = new Dictionary<int, int>();
        foreach (var factor in mFactors)
        {
            if (hash.ContainsKey(factor))
                hash[factor]++;
            else
                hash.Add(factor, 1);
        }
        return hash;
    }

To test method, I am using following code

[Test]
    public void LeastCommonMultipleByPrimeFactorizationPositiveTest()
    {
        Assert.AreEqual(42, ArthmeticProblems.LeastCommonMultipleByPrimeFactorization(21, 6));

        Assert.AreEqual(12, ArthmeticProblems.LeastCommonMultipleByPrimeFactorization(4, 6));
    }

Note: This is just for fun and revision of my basic concepts

Answer 1

IsPrime

public static bool IsPrime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i == n)
                return true;
            else
                return false;
        }
    }
    return false;
}

Under what circumstances can the final return false be reached? Why not handle those special cases explicitly, and then simplify the loop body by reducing it?

public static bool IsPrime(int n)
{
    if (n < 1) throw new ArgumentException("n");
    if (n == 1) return false;

    for (int i = 2; i < n; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}

Of course, there are better ways of testing primality than trial division, but that's beside the point.

PrimeFactors

public static int[] PrimeFactors(int n)
{
    var factors = new List<int>();
    for (int i = 2; i <= n; i++)
    {
        while (n % i == 0 && IsPrime(i))
        {
            factors.Add(i);
            n = n / i;
        }
    }
    return factors.ToArray();
}

Any particular reason for returning int[] instead of IEnumerable<int>?

What's the purpose of the IsPrime call there? It's easy to prove that it always returns true (and so the IsPrime method isn't needed at all).

As a point of style, I prefer op= methods, but this is really subjective.

The loop guard might be more intelligible as n > 1.

public static IEnumerable<int> PrimeFactors(int n)
{
    var factors = new List<int>();
    for (int i = 2; n > 1; i++)
    {
        while (n % i == 0)
        {
            factors.Add(i);
            n /= i;
        }
    }
    return factors;
}

CreateCounterHash

private static Dictionary<int, int> CreateCounterHash(IEnumerable<int> mFactors)
{
    Dictionary<int, int> hash = new Dictionary<int, int>();
    foreach (var factor in mFactors)
    {
        if (hash.ContainsKey(factor))
            hash[factor]++;
        else
            hash.Add(factor, 1);
    }
    return hash;
}

Why does the return type use the implementation Dictionary rather than the interface IDictionary?

Why hard-code the type? You don't do anything with it other than equality checking, so it could be IDictionary<T, int> CreateCounterHash<T>(IEnumerable<T> elts) (and then could potentially be an extension method of IEnumerable<T>).

ContainsKey followed by a get is a minor inefficiency. Since TryGetValue will give default(int) (i.e. 0) if the key isn't, found, this can be fixed:

private static IDictionary<T, int> CreateCounterHash<T>(IEnumerable<T> elts)
{
    Dictionary<T, int> hash = new Dictionary<T, int>();
    foreach (var elt in elts)
    {
        int currCount;
        hash.TryGetValue(elt, out currCount);
        hash[elt] = currCount + 1;
    }
    return hash;
}

LCM

public static int LeastCommonMultipleByPrimeFactorization(int m, int n)
{
    //retrieve prime factors for both numbers
    int[] mFactors = PrimeFactors(m);
    int[] nFactors = PrimeFactors(n);

    //generate hash code to get counter for each factor 
    var mFactorsCountHash = CreateCounterHash(mFactors);
    var nFactorsCountHash = CreateCounterHash(nFactors);

    var primeFactors = new List<int>();
    primeFactors.AddRange(mFactors);
    primeFactors.AddRange(nFactors);

    int result = 1;

    //On each distinct factor... check either which number factors 
    foreach (int factor in primeFactors.Distinct())
    {
        int mfactorCount = 0;
        int nfactorCount = 0;
        if (mFactorsCountHash.ContainsKey(factor))
        {
            mfactorCount = mFactorsCountHash[factor];
        }

        if (nFactorsCountHash.ContainsKey(factor))
        {
            nfactorCount = nFactorsCountHash[factor];
        }

        int numberOfCount = mfactorCount > nfactorCount ? mfactorCount : nfactorCount;
        result = factor * result * numberOfCount;
    }

    return result;
}

Looks buggy: factor * numberOfCount will only be correct when numberOfCount == 1 or factor == 2 && numberOfCount == 2.

Also a tad repetitive. Can't you merge the two counts earlier?

public static IDictionary<K, V> MergeDictionaries<K, V>(IDictionary<K, V> d1,
                                                        IDictionary<K, V> d2,
                                                        Func<V, V, V> mergeFunc)
{
    // Left as an exercise
    // Only call mergeFunc when both dictionaries contain the key
}

You can also use a bit of Linq to do the aggregate, so the LCM simplifies to

public static int LeastCommonMultipleByPrimeFactorization(int m, int n)
{
    //retrieve prime factors for both numbers
    int[] mFactors = PrimeFactors(m);
    int[] nFactors = PrimeFactors(n);

    //generate hash code to get counter for each factor 
    var mFactorsCountHash = CreateCounterHash(mFactors);
    var nFactorsCountHash = CreateCounterHash(nFactors);

    var combinedCounts = MergeDictionaries(mFactorsCountHash, nFactorsCountHash, Math.Max);
    return combinedCounts.Aggregate(1, (prod, primeWithMult) => prod * pow(primeWithMult.Key, primeWithMult.Value));
}

Answer 2

You don't need to determine whether the factor is a prime when you factorize a number, the divide method itself guarantee the factor is prime. I have a solution with few code, but not in good performance, and with a limitation of the number less than 1000, so it's just for your reference, the solution use an array to store the factors of a number, the index of the array indicates the factor, and the value of array[index] is the times of that factor, for example factor[3] = 2, means the number has a factor 3 occurs twice.

// Factorize number n
static int[] Factorize(int n)
{
    int[] factors = new int[1000];

    for (int i = 2; n > 1; )
    {
        if (n % i == 0)
        {
            factors[i]++;
            n /= i;
        }
        else
            ++i;
    }

    return factors;
}

// Find the Least common multiple of number a and b
static int LCM(int a, int b)
{
    int[] factorsA = Factorize(a);
    int[] factorsB = Factorize(b);

    int result = 1;
    for (int m = 0; m < factorsA.Length; ++m)
    {
        if (factorsA[m] + factorsB[m] != 0)
        {
            if (factorsA[m] > factorsB[m])
                result *= (int)Math.Pow(m, factorsA[m]);
            else
                result *= (int)Math.Pow(m, factorsB[m]);
        }
    }
    return result;
}

Answer 3

Your code is very inefficient, because it uses a naive algorithm for finding prime numbers, and performs primality checks for the same number multiple times.

A better approach would pre-compute a table of primes, and use numbers from it for all further checking.

Here is how you can make a table of prime numbers suitable for use with ints:

private static readonly ISet<int> Primes = new SortedSet<int>{ 2 };

static MyClass() {
    var cand = 3;
    while (cand*cand > 0) {
        var ok = true;
        foreach (var p in Primes) {
            if (cand % p == 0) {
                ok = false;
                break;
            }
            if (p*p > cand) {
                break;
            }
        }
        if (ok) {
            Primes.Add(cand);
        }
        cand += 2;
    }
}

With the set of primes in hand, your first two functions become much simpler, and orders of magnitude faster:

public static bool IsPrime(int n) {
    return Primes.Contains(n);
}

public static int[] PrimeFactors(int n) {
    var res = new List<int>();
    foreach (var p in Primes) {
        while (n % p == 0) {
            res.Add(p);
            n /= p;
        }
        if (n == 1) break;
    }
    return res.ToArray();
}