Prime numbers, Prime Factors and LCM

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 ();
for (int i = 2; i ();
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 CreateCounterHash(IEnumerable mFactors)
{
Dictionary hash = new Dictionary();
foreach (var factor in mFactors)

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();
    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?

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 PrimeFactors(int n)
{
    var factors = new List();
    for (int i = 2; n > 1; i++)
    {
        while (n % i == 0)
        {
            factors.Add(i);
            n /= i;
        }
    }
    return factors;
}

CreateCounterHash

private static Dictionary CreateCounterHash(IEnumerable mFactors)
{
    Dictionary hash = new Dictionary();
    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 CreateCounterHash(IEnumerable elts) (and then could potentially be an extension method of IEnumerable).

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 CreateCounterHash(IEnumerable elts)
{
    Dictionary hash = new Dictionary();
    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();
    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 MergeDictionaries(IDictionary d1,
                                                        IDictionary d2,
                                                        Func 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));
}

StackExchange Code Review Q#17662, answer score: 3