3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ If you search for factors in increasing order in IsPrime and you reach a point where your i*i > n, you can safely stop your search (do you understand why that is the case?) Using this simple trick will help you drastically shorten the time it takes to test larger numbers for being prime. \$\endgroup\$ – dasblinkenlight Oct 18 '12 at 14:17
  • \$\begingroup\$ you can change for (int i = 2; i <= n; i++) to for (int i = 2; i <= Convert.ToInt32(Math.Floor(Math.Sqrt(n))); i++) in the first snippet \$\endgroup\$ – Ron Klein Oct 18 '12 at 15:38
3
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ +1. Thanks Peter. Is there alternative approach you can think of for LeastCommonMultipleByPrimeFactorization. \$\endgroup\$ – Adil Mughal Oct 18 '12 at 13:33
  • \$\begingroup\$ @AdilMughal, there's the obvious approach of not using prime factorisation, but you've explicitly chosen not to use gcd. \$\endgroup\$ – Peter Taylor Oct 18 '12 at 15:47
  • \$\begingroup\$ since it's just for self-learning and fun, that's why I also tried that. But what I meant with alternative was any better approach to do with prime factorization \$\endgroup\$ – Adil Mughal Oct 18 '12 at 16:14
  • \$\begingroup\$ You could also skip a larger number of tests in the IsPrime function by using the Math.Sqrt(n) in the for statement ... for (int i = 2; i <= Math.Sqrt(n); i++) \$\endgroup\$ – Gene S Oct 18 '12 at 16:20
  • \$\begingroup\$ @GeneS, true, although that's the worst possible way of doing the early escape. I didn't focus too much on IsPrime because I knew I was going to point out that it's unnecessary. \$\endgroup\$ – Peter Taylor Oct 18 '12 at 16:25
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I like your approach. The only thing we would lose its extra space...int[1000]. Plus few queries: -Is 1000 definite? - for (int m = 0; m < factorsA.Length; ++m) would that work if factorsB length is greater than factorsA ? \$\endgroup\$ – Adil Mughal Oct 18 '12 at 14:00
  • \$\begingroup\$ Yes, you are right, the solution won't work if a or b is 1001, may be we can use a list to store a key-value pair where the key is the factor and the value is the times of that factor, but that will make the code more complexity, I like simple code :) \$\endgroup\$ – zdd Oct 18 '12 at 14:03
2
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ Can you please explain a bit MyClass method? Also I am a bit more curious about LCM method. \$\endgroup\$ – Adil Mughal Oct 18 '12 at 15:04
  • \$\begingroup\$ @AdilMughal MyClass is the static constructor of your class. Since your code does not show the name of your class, I called your class MyClass (I hope this makes sense). Even if you keep your LCM method as is, replacing the first two methods will make it go significantly faster. P.S. Did you prove the i*i > n question from my comment? My code is using this fact on the p*p > cand line. \$\endgroup\$ – dasblinkenlight Oct 18 '12 at 15:15
  • \$\begingroup\$ When this would end? while (cand*cand > 0) \$\endgroup\$ – Adil Mughal Oct 18 '12 at 15:32
  • \$\begingroup\$ @AdilMughal Ah, that's a very good question: it will end when the integer overflows, so multiplication of two positive numbers produces a negative result. \$\endgroup\$ – dasblinkenlight Oct 18 '12 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.