高效地找出一个数的所有因子

Question

高效地找出一个数的所有因子

11

我想找到给定数的所有因数（除了这个数本身）。

目前我有以下代码：

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    toreturn.Add(1);
    int i = 0;
    int j=1;
    int z = 0;
    while (primes.ElementAt(i) < Math.Sqrt(x))
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            toreturn.Add(x / primes.ElementAt(i));
            j = 2;
            z = (int)Math.Pow(primes.ElementAt(i), 2);
            while (z < x)
            {
                if (x % z == 0)
                {
                    toreturn.Add(z);
                    toreturn.Add(x / z);
                    j++;
                    z = (int)Math.Pow(primes.ElementAt(i), j);
                }
                else
                {
                    z = x;
                }
            }
        }
        i++;
    }
    toreturn = toreturn.Distinct().ToList<int>();
    return toreturn;
}

假设primes是一个质数列表（假定它是正确的，并且足够大）。该算法能够找到所有的质因子，但不是所有的因子（即对于给定的数字34534，它会返回{1,2,17267,31,1114}，但会错过{62, 557}，因为62是一个组合，因此也错过了557。

我也尝试过仅获取一个数的质因子，但我不知道如何将其转换为所有正确组合的列表。

该算法的代码如下：

public static List<int> prime_factors(int x)
{
    List<int> toreturn = new List<int>();
    int i = 0;
    while (primes.ElementAt(i) <= x)
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            x = x / primes.ElementAt(i);
        }
        else
        {
            i++;
        }
    }
    return toreturn;
}

任何想法如何修复第一个问题，或者如何从第二个问题中创建组合列表（我更喜欢这样做，因为它会更快）？

- soandos

可能是在C#中找到给定数字的所有因子的最佳方法的重复问题。 - MxNx

我发现这篇帖子也很有帮助- https://codereview.stackexchange.com/questions/237416/c-code-to-find-all-divisors-of-an-integer?newreg=2fdcd819f7b443b9800dfed0f1f3d80c - BUDDHIKA

2个回答

5

之前有一个类似的问题（点击此处），其中提供了一种使用IEnumerable解决方案。如果你需要找到所有约数而不是因子，并且假设你至少在使用C# 3.0，则可以使用以下代码：

static IEnumerable<int> GetDivisors(int n)
{
    return from a in Enumerable.Range(2, n / 2)
           where n % a == 0
           select a;                      
}

然后像这样使用它：

foreach(var divisor in GetDivisors(10))
    Console.WriteLine(divisor);

或者，如果您想要一个列表，只需：

List<int> divisors = GetDivisors(10).ToList();

- LazyOfT

再次强调，这是一种不错的暴力解法。但是，考虑到我已经有了必要的质数列表，没有理由这样做。 - soandos

所以，如果您已经拥有了数字的所有质因数，并且只想要它们之间的所有组合，为什么不使用笛卡尔积呢？类似这样：from x in primes from y in primes where x != y select x * y？这可以解决您的问题，前提是您的质数中有1（否则.Concat(primes)将解决该问题）。 - LazyOfT

但我需要相乘的因数数量是未知的。它可能是三个或更多... - soandos

1

我明白你的意思。你所问的是一种获取已有质因数所有可能组合的方法。这可以通过某些组合算法来解决，但在我的观点中，这并不是那么简单的事情。除此之外，你可能会冒着采用试图优化速度的解决方案的风险，而导致比较简单的方法更低效且难以读懂。也许你应该先考虑编写一个可读性强的解决方案，如果其性能不能满足给定任务，则再尝试进行优化。 - LazyOfT

这种方法在搜索质数的因子时不起作用。例如，对于 n=5，它会返回一个空列表！ - Nikolay Kostov

@NikolayKostov 我没有尝试过这段代码，但我认为如果将 Enumerable.Range(2, n / 2) 更改为 Enumerable.Range(1, n / 2)，那么问题就会得到解决。 - David Winiecki

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rodrick Chapman · Accepted Answer

既然您已经有了质因数列表，那么您需要做的就是计算该列表的幂集。

现在，一个问题是列表中可能会有重复项（例如，20的质因数= 2 * 2 * 5），但集合不允许重复项。因此，我们可以通过将每个列表元素投影到形式为{x，y}的结构中使其唯一，其中x是质数，y是质数在列表中的索引。

var all_primes = primes.Select((x, y) => new { x, y }).ToList();

现在，all_primes是一个形如{x,y}的列表，其中x是质数，y是列表中的索引。

然后我们计算幂集（GetPowerSet的定义如下）：

var power_set_primes = GetPowerSet(all_primes);

因此，power_set_primes 是一个 IEnumerable<IEnumerable<T>>，其中 T 是匿名类型 {x, y}，其中 x 和 y 的类型为 int。

接下来，我们计算幂集中每个元素的乘积。

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

将所有内容整合在一起：

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates.
var power_set_primes = GetPowerSet(all_primes);
var factors = new HashSet<int>();

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

从 http://rosettacode.org/wiki/Power_Set 获取幂集的实现。

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}