如何创建一个计算C＃中整数因子的算法？

Question

我需要提出的算法是计算用户输入数字的所有因子的算法，例如用户输入“50”，程序将显示所有50的因子，它们是：1，2， 5，10，25，50.

该程序需要适用于所有正整数值。

有人愿意告诉我该怎么做吗？这不是家庭作业，它只是研究材料，我一直在试图找出这个问题超过2小时。我应该使用数组吗？

Answer 1

这里有一个线索：如果Y/X没有余数，则数字X是Y的因子。另一个线索：在大多数语言中都有通用的数学运算符来发现一个数除以另一个数是否有余数。

Answer 2

我想你需要给我们更多的信息。你的算法有什么要求？它是否必须有一个特别好的运行时间？你有什么功能可以访问？

如果没有限制，我会说只是循环通过整数x小于输入，并检查是否输入/ x是整数，如果是这样，那么x是一个因子。

Answer 3

天真的算法是尝试用小于Math.Sqrt(n) + 0.5的所有数字来划分（或检查余数）输入数字n。这对学习很好。

因此，在伪代码：

integer n from user input 
for each integer i in the range 1 to sqrt(n) + 1/2 do 
    r = remainder of n divided by i 
    if r is zero print i and n/i 

Answer 4

首先，尝试天真/蛮力的方法。

例如，您可以遍历1和用户提供的[希望相对较小]的数字之间的所有数字，并检查它是否平均分配这个数字。

顺便说一句，您可以使用模运算符断言给定的整数可以被另一个整数（或更确切地说，模运算的结果应该是一个特定值）完全整除的事实。

一旦你有这个工作，你可以想到迭代中的一些数字可以被消除的方式。这种方法在解决问题中并不罕见：
  1）以天真的方式解决问题，并且
  2）寻找减少/过滤/修剪并以其他方式改进朴素方法的方法。
如果没有别的办法，天真的方法提供了一个很好的基线，而且，因为它也更简单，它也可以用来验证更复杂方法的输出。

一旦你玩了这个解决方案，你可以尝试一个独特的方法。这个想法是将数字分解为主要因素。在这个例子中，50会给出（1，2，5，5，50），然后你需要枚举这些素数因子的所有组合（不包括微不足道的1和50）。素数因子分解通常应该是直截了当的（考虑在早期的数学课中学习它的方式），但列举所有可能的组合可能会导致暂停一点（然而这是继续进入的算法的类型时尚或其他CS应用程序）。

Answer 5

我可能会更简单。NET版本：

int factor = 3447; // Input 
List<int> results = new List<int>(); 
for (int i=1; i<factor; i++) { 
    for (int j=1; j<factor; j++) { 
     if (i % j == 0) { 
      results.Add(i); 
      break; 
     } 
    } 
} 

这应该会产生预期结果。它通过递增地遍历从1到X的所有数字（数字到因子）。内循环通过同一组数字来查看模数是否为零（无余数）。一旦发现我们继续前进，否则我们会得到重复。

另请注意，这是一种最坏情况（强力）算法。

Answer 6

我假设你已经编写了程序，但是有w/e。

％operator是你的朋友在这里。

x％y = 0当且仅当x可被y整除（意味着没有余数，意味着y是x的一个因子）。

在C＃中，拿到50的因素，下面的操作必须是真实的：

if(50 % x == 0) 
     Console.WriteLine(x + " is a factor of 50"); 

这里是从1到100获得的50因素的野蛮方式：

 int toTest = 50; 
    for(int x = 1; x < toTest; x++) 
    { 
     if(toTest % x == 0) 
      Console.WriteLine(x + " is a factor of 50"); 
    }