素数、素数与LCM

Question

我试图通过素因式分解来生成LCM。我已经做了相反的方法来生成使用GCD的LCM，但是我试图使用素因式分解来实现它。

我得到了正确的素因子，但问题是，要生成LCM，我们需要将每个因子乘以，在任何一个数的因子中，都会出现最大的次数。参考文献

现在，我不喜欢我为实现这个目标而提出的代码。逻辑是检索这两个数字的因子，然后为每个因素创建一个散列/计数器。最后，将该因子与到目前为止的结果以及每个散列计数器列表中最多的次数相乘。

我想回顾一下我所有的方法IsPrime，PrimeFactors，LeastCommonMultipleByPrimeFactorization等等，特别是主要的LeastCommonMultipleByPrimeFactorization方法。请随时提供您的意见和建议。我很乐意看到一些最简单的方法来实现这一点。

代码片段：

    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;
    }

为了测试方法，我使用以下代码

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

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

注:这只是为了好玩和修改我的基本概念。

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;
}

在什么情况下才能达到最终的return false？为什么不显式地处理这些特殊情况，然后通过减少循环体来简化它呢？

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;
}

当然，有比审判分工更好的测试原始性的方法，但这不是重点。

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

返回int[]而不是IEnumerable<int>有什么特别的原因吗？

IsPrime在那里的目的是什么？很容易证明它总是返回true (因此根本不需要IsPrime方法)。

作为风格的一点，我更喜欢op=方法，但这确实是主观的。

循环保护可能更容易理解为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;
}

为什么返回类型使用实现Dictionary而不是接口IDictionary？

为什么要硬编码这个类型？除了等式检查之外，您不会对它做任何事情，所以它可以是IDictionary<T, int> CreateCounterHash<T>(IEnumerable<T> elts) (然后可能是IEnumerable<T>的扩展方法)。

ContainsKey后面跟着一个get是一个小的低效率。由于TryGetValue将给出default(int) (即0)，如果键不是，则可以修复：

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;
}

看起来很糟糕：factor * numberOfCount只有在numberOfCount == 1或factor == 2 && numberOfCount == 2时才是正确的。

还有一点重复。你不能早点把这两笔钱合并吗？

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
}

您还可以使用一些Linq来进行聚合，因此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 combinedCounts = MergeDictionaries(mFactorsCountHash, nFactorsCountHash, Math.Max);
    return combinedCounts.Aggregate(1, (prod, primeWithMult) => prod * pow(primeWithMult.Key, primeWithMult.Value));
}

Answer 2

在分解一个数字时，不需要确定这个因子是否是素数，除法本身就可以保证因子是素数。我有一个解决方案，代码很少，但性能不佳，并且限制在1000以内，所以这只是供您参考，解决方案使用数组来存储数字的因子，数组的索引表示因子，数组索引的值是该因子的倍数，例如，因子3.= 2，意味着这个数字有一个因子3发生了两次。

// 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

您的代码效率很低，因为它使用天真的算法来查找素数，并多次对相同的数字执行素数检查。

一种更好的方法是预先计算一个素数表，并使用其中的数字进行所有进一步的检查。

下面是如何制作一个适合与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;
    }
}

在掌握了一组素数之后，您的前两个函数变得简单得多，数量级更快：

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