寻找给定数字的所有因数的最佳方法

Question

寻找给定数字的所有因数的最佳方法

36

所有能够整除x的数字。

我输入4，它返回：4、2、1。

编辑：我知道这听起来像作业。我正在编写一个小应用程序，用于使用半随机测试数据填充一些产品表。其中两个属性是ItemMaximum和Item Multiplier。我需要确保乘数不会创建一个不合逻辑的情况，即购买1个以上的物品将使订单超过允许的最大值。因此，这些因数将提供一个有效值列表，供我的测试数据使用。

编辑++：在得到大家的帮助后，我选择了以下内容。再次感谢！

编辑＃：我编写了3个不同的版本，以查看哪个更好，并针对分解小数和非常大的数字进行了测试。我将粘贴结果。

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

private IEnumerable<int> GetFactors3(int x)
{            
    for (int factor = 1; factor * factor <= x; factor++)
    {
        if (x % factor == 0)
        {
            yield return factor;
            if (factor * factor != x)
                yield return x / factor;
        }
    }
}

private IEnumerable<int> GetFactors1(int x)
{
    int max = (int)Math.Ceiling(Math.Sqrt(x));
    for (int factor = 1; factor < max; factor++)
    {
        if(x % factor == 0)
        {
            yield return factor;
            if(factor != max)
                yield return x / factor;
        }
    }
}

对于数字20，每个数字分解5次：

GetFactors1-445,881
GetFactors2-308,234
GetFactors3-913,659

对于数字20000，每个数字分解5次：

GetFactors1-5,644,457
GetFactors2-12,117,938
GetFactors3-3,108,182

- Echostorm

2

你应该知道，现在还没有一种通用的高性能解决方案来解决这个问题。现代密码学依赖于不存在这样的解决方案。 - Steve McLeod

1

是的，但我不确定是否有比逐个测试数字更好的方法，因为我已经很久没有上数学课了。 - Echostorm

与Python相关的问题：python - tzot

一个简单的WinForm应用程序，可以帮助您找到数字因子。https://findingnumberfactors.codeplex.com - Iman

14个回答

21

%（余数）操作符是这里要使用的。如果x % y == 0，那么x可被y整除。(假设0 < y <= x)。我个人会将其实现为一个返回IEnumerable<int>的方法，采用迭代器块实现。

- Jon Skeet

% 实际上是取模运算符，而不是“余数”。IEnumerable<int> 块具有上限，这使得它在分解“小”的（计算）数字方面非常实用。 - Kraang Prime

@SamuelJackson：C# 5语言规范第5.8.3节和Eric Lippert的博客文章存在分歧。你在MSDN上的参考是JScript，而不是C#。 - Jon Skeet

请查看C#运算符 - 在“乘法运算符”部分中，它被称为“模数”，在“赋值和Lambda运算符”下，它说明了“模数赋值。将x的值除以y的值，将余数存储在x中，并返回新值。”虽然模数计算技术上是除数所有可能除法后剩余的部分，但这个操作的正确数学术语（以及在c#文档中）是模数，有些人将其称为模运算。 :) - Kraang Prime

@Samuel：你提到的那个指南不是规范。我认为规范才是最权威的资料。如果你想忽略它，那可以自行选择，但我会把它作为我的参考资料。我肯定不会修改我的帖子。 - Jon Skeet

@SamuelJackson：是的，这是IL中给出的名称 - 这与C#无关。（这是一个Interop问题。）请注意，在规范中，“modulus”一词只出现了一次，而在运算符中它一直使用“remainder”一词，包括在章节标题中。规范中没有任何地方称其为模数运算符。虽然规范的下载页面确实提到了C#参考指南，但规范本身并没有。据我所知，C#参考指南不是由语言设计师维护的，他们对此有最终决定权。 - Jon Skeet

显示剩余3条评论

14

虽然很晚，但是之前被接受的答案并没有给出正确的结果。

感谢Merlyn，我现在知道为什么在更正后的示例中会有一个“最大值”方框了。尽管来自Echostorm的答案似乎更完整。

public static IEnumerable<uint> GetFactors(uint x)
{
    for (uint i = 1; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            yield return i;
            if (i != x / i)
                yield return x / i;
        }
    }
}

- call me Steve

1

需要在for循环后添加以下内容以返回x本身。一个数字总是它自己的因子。yield return x; - Suraj

我认为之前可能存在的任何问题现在都已经得到解决。停在平方根处的原因是因为它已经检查过平方根以下的所有可能的因数（这对于乘以大于“max”的任何数字是必要的），以及平方根以上的任何数字（由于它输出每次迭代中的配对两边以获得结果）。输出时仍未输出的最大可能值是平方根。 - Merlyn Morgan-Graham

1

例如，如果你得到了81的因数，那么在10到40之间的循环迭代是浪费的。当你输出3时，你已经输出了27，如果你没有输出两边，如果你在81/2（40）停止，你永远不会得到81作为一个因数。 - Merlyn Morgan-Graham

谢谢！现在确实有意义了。 - call me Steve

我会缓存 x / i 而不是重复计算它两次。 - Bip901

4

作为扩展方法：

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        return from potentialFactor in Enumerable.Range(1, i)
               where potentialFactor.Divides(i)
               select potentialFactor;
    }

这是一个使用示例：

        foreach (int i in 4.Factors())
        {
            Console.WriteLine(i);
        }

请注意，我已经进行了优化以达到清晰易懂的效果，而非追求性能。对于较大的i值，此算法可能需要很长时间才能完成。

- Jay Bazuzi

3

另一种LINQ风格，旨在保持O(sqrt(n))的复杂度。

        static IEnumerable<int> GetFactors(int n)
        {
            Debug.Assert(n >= 1);
            var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1)))
                    where n % i == 0
                    select new { A = i, B = n / i };

            foreach(var pair in pairList)
            {
                yield return pair.A;
                yield return pair.B;
            }


        }

- pablito

2

我采用了简单的方式进行操作。虽然我并不是很懂，但有人告诉过我：简单有时也可以意味着优雅。以下是一种可能的方法：

    public static IEnumerable<int> GetDivisors(int number)
    {
        var searched = Enumerable.Range(1, number)
             .Where((x) =>  number % x == 0)
             .Select(x => number / x);

        foreach (var s in searched)          
            yield return s;
    }

编辑: 正如Kraang Prime所指出的那样，此函数不能超过整数限制，并且（诚然）不是处理此问题最有效的方法。

- Spencer

这只能处理整数限制内的因子。 - Kraang Prime

2

@spencer 只是好奇为什么你在 foreach 循环中使用 yield return，因为你已经有了一个 IEnumerable<int>，为什么不直接返回 Linq 查询的结果，而要将其赋值给 searched？ - Rodney S. Foley

2

这里再次提供代码，只计算平方根，正如其他人所提到的。如果你希望提高性能，我想人们会被这个想法吸引。但我更愿意先编写优雅的代码，在测试软件后再进行性能优化。

不过，为了参考，这是代码：

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i))
                               where potentialFactor.Divides(i)
                               select potentialFactor)
        {
            yield return result;
            if (i / result != result)
            {
                yield return i / result;
            }
        }
    }

这种方式不仅使结果难以阅读，而且因此因素的顺序也会混乱。

- Jay Bazuzi

2

因为它们是两个不同的答案，具有不同的优点。 - Jay Bazuzi

1

还有一种解决方案。不确定除了易读性以外是否有其他优点..:

List<int> GetFactors(int n)
{
    var f = new List<int>() { 1 };  // adding trivial factor, optional
    int m = n;
    int i = 2;
    while (m > 1)
    {
        if (m % i == 0)
        {
            f.Add(i);
            m /= i;
        }
        else i++;
    }
    // f.Add(n);   // adding trivial factor, optional
    return f;
}

- TaW

我建议提供更具描述性的变量名称以进一步增强可读性。 - EnterTheCode

这个似乎有些不对劲。例如，42的因数应该返回一个包含8个值的列表。1、2、3、6、7、14、21和42...但是对我来说，这个函数只返回1、2、3和7。只是想让你知道一下。 - Ocean Airdrop

1

我来这里只是为了寻找解决我的问题的方法。经过查看以前的回复，我想即使我可能有点晚到派对上，也可以提供自己的答案。

一个数的因子数量最多不会超过该数的一半。没有必要处理浮点值或像平方根这样的超越运算。此外，找到一个数的因子就自动找到了另一个。只需找到一个因子，通过将原始数除以已找到的因子即可返回两个因子。

我怀疑我自己的实现不需要使用检查，但我包括它们只是为了完整性（至少部分地）。

public static IEnumerable<int>Factors(int Num)
{
  int ToFactor = Num;

  if(ToFactor == 0)
  { // Zero has only itself and one as factors but this can't be discovered through division
    // obviously. 
     yield return 0;
     return 1;
  }
    
  if(ToFactor < 0)
  {// Negative numbers are simply being treated here as just adding -1 to the list of possible 
   // factors. In practice it can be argued that the factors of a number can be both positive 
   // and negative, i.e. 4 factors into the following pairings of factors:
   // (-4, -1), (-2, -2), (1, 4), (2, 2) but normally when you factor numbers you are only 
   // asking for the positive factors. By adding a -1 to the list it allows flagging the
   // series as originating with a negative value and the implementer can use that
   // information as needed.
    ToFactor = -ToFactor;
    
    yield return -1;
   }
    
  int FactorLimit = ToFactor / 2; // A good compiler may do this optimization already.
                                  // It's here just in case;
    
  for(int PossibleFactor = 1; PossibleFactor <= FactorLimit; PossibleFactor++)
  {
    if(ToFactor % PossibleFactor == 0)
    {
      yield return PossibleFactor;
      yield return ToFactor / PossibleFactor;
    }
  }
}

- Richard Robertson

1

如果您使用双精度浮点数，以下代码可以工作：使用for循环从1开始迭代到要因数分解的数字。在每个迭代中，将要因数分解的数字除以i。如果（number / i）％1 == 0，则i是一个因数，数字/ i的商也是因数。将其一个或两个放入列表中，然后您就拥有了所有的因数。

- JEJoll

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

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

- Chris Marasti-Georg · Accepted Answer

伪代码：

从1到数字的平方根循环，将索引称为“i”。
如果数字模以i为0，则将i和数字/i添加到因子列表中。

真实代码：

public List<int> Factor(int number) 
{
    var factors = new List<int>();
    int max = (int)Math.Sqrt(number);  // Round down

    for (int factor = 1; factor <= max; ++factor) // Test from 1 to the square root, or the int below it, inclusive.
    {  
        if (number % factor == 0) 
        {
            factors.Add(factor);
            if (factor != number/factor) // Don't add the square root twice!  Thanks Jon
                factors.Add(number/factor);
        }
    }
    return factors;
}

正如Jon Skeet所提到的，您也可以将其实现为IEnumerable<int>，而不是添加到列表中，请使用yield。使用List<int>的优点是如果需要，可以在返回之前对其进行排序。但是，您也可以使用混合方法获取已排序的枚举器，在每次循环迭代时产生第一个因子并存储第二个因子，然后以相反顺序产生每个存储的值。

您还需要对传递给函数的负数进行处理。