给定一个数字，找出它的因数的算法。最短的方法是什么？

Question

有什么简单而高效的逻辑可以找出给定数字的因数吗？是否存在基于此的算法。

事实上，我真正的问题是找出给定数字存在的因数数量。

请告诉我任何算法，谢谢。

谢谢。

- AGeek

---

代码长度短还是执行时间短？ - meriton

这个问题是受到projecteuler问题的启发吗？ - Maciej Hehl

@Meriton - 在找到解决方案方面最短的时间内。 - AGeek

@Maciej - 好吧，这是另一个问题的子问题。没有受到任何启发。 - AGeek

这个“给定的数字”可以有多大？ - Maciej Hehl

找到一个快速算法来完成这个任务可能会让你陷入麻烦。事实上，因子分解的困难性是公钥加密算法（如RSA）所依赖的。 - Hans Passant

Answer 1

实际上，我的真正问题是找出给定数字存在的因数数量。

好的，这有所不同。让n是给定的数字。

如果n = p1^e1 * p2^e2 * ... * pk^ek，其中每个p都是质数，则n的因子数量为(e1 + 1)*(e2 + 1)* ... *(ek + 1)。更多信息请参见此处。

因此，只需找到每个质因数出现的幂即可。例如：

read given number in n
initial_n = n
num_factors = 1;
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number
{
    power = 0; // suppose the power i appears at is 0
    while (n % i == 0) // while we can divide n by i
    {
        n = n / i // divide it, thus ensuring we'll only check prime factors
        ++power // increase the power i appears at
    }
    num_factors = num_factors * (power + 1) // apply the formula
}

if (n > 1) // will happen for example for 14 = 2 * 7
{
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2
}

例如，取18。 18 = 2^1 * 3*2 => 因子数量 = (1 + 1)*(2 + 1) = 6。确实，18的6个因子是1, 2, 3, 6, 9, 18。

这是我的方法和@Maciej描述和发布的方法之间的小基准测试。他的方法具有更易于实现的优点，而我的方法在只迭代质数时更快，就像我为此测试所做的那样。

 class Program
{
    static private List<int> primes = new List<int>();

    private static void Sieve()
    {
        bool[] ok = new bool[2000];

        for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually)
        {
            if (!ok[i])
            {
                primes.Add(i);

                for (int j = i; j < 2000; j += i)
                    ok[j] = true;
            }
        }
    }

    private static int IVlad(int n)
    {
        int initial_n = n;
        int factors = 1;

        for (int i = 0; primes[i] * primes[i] <= n; ++i)
        {
            int power = 0;
            while (initial_n % primes[i] == 0)
            {
                initial_n /= primes[i];
                ++power;
            }
            factors *= power + 1;
        }

        if (initial_n > 1)
        {
            factors *= 2;
        }

        return factors;
    }

    private static int Maciej(int n)
    {
        int factors = 1;
        int i = 2;
        for (; i * i < n; ++i)
        {
            if (n % i == 0)
            {
                ++factors;
            }
        }

        factors *= 2;

        if (i * i == n)
        {
            ++factors;
        }

        return factors;
    }

    static void Main()
    {
        Sieve();


        Console.WriteLine("Testing equivalence...");

        for (int i = 2; i < 1000000; ++i)
        {
            if (Maciej(i) != IVlad(i))
            {
                Console.WriteLine("Failed!");
                Environment.Exit(1);
            }
        }

        Console.WriteLine("Equivalence confirmed!");

        Console.WriteLine("Timing IVlad...");
        Stopwatch t = new Stopwatch();

        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            IVlad(i);
        }

        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
        Console.WriteLine("Timing Maciej...");

        t.Reset();
        t.Start();
        for (int i = 2; i < 1000000; ++i)
        {
            Maciej(i);
        }


        Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds);
    }
}

我的机器上的结果：

测试等价性...
确认等价性！
计时IVlad...
总毫秒数：2448
计时Maciej...
总毫秒数：3951
按任意键继续. . .

- IVlad

---

是的，关键在于意识到每个因子都有其对应因子，并且只需循环到平方根。但是如果一个人无论如何都要从2循环到平方根，检查每个i是否能够整除n，计算幂并将n除以i是浪费时间的，我认为最好的方法是仅增加因子计数器。 - Maciej Hehl

如果i是n的因子，那么n / i也是它的因子。这是另一种方法，也允许只进行到平方根，只需确保i和n / i不同，以便不重复计算！但是，这不能让你只检查质数，所以我认为它不总是更快（使用我的发布方法，您可以预先计算质数以使其更快）。例如，对于20，您必须检查4才能意识到在您描述的方法中4和5是因子（如果我想到的是同一件事情）。 - IVlad

Answer 2

有大量的算法可用 - 从简单的试除法到针对大数的非常复杂的算法。请查看维基百科上的整数分解，选择适合您需求的算法。

这里是一个简短但效率低下的C#实现，可以找到质因子的数量。如果您需要因子的数量（而不是质因子），则必须存储带有其重复性的质因子，并在此之后计算因子的数量。

var number = 3 * 3 * 5 * 7 * 11 * 11;

var numberFactors = 0;
var currentFactor = 2;

while (number > 1)
{
    if (number % currentFactor == 0)
    {
        number /= currentFactor;
        numberFactors++;
    }
    else
    {
        currentFactor++;
    }
}

- Daniel Brückner

---

这是错误的。你在数什么，因子还是质因子？这会给你18的3个因子，无论如何都是错误的。 - IVlad

numberFactors计算素因子的数量，但我的答案表明因子的数量可以从素因子及其重复性中推导出来。 - Daniel Brückner

你说你的解决方案计算质因数是错误的！numberFactors将包含值 3（对于 18），这是错误的，18中只有2个质因数：2和3。 - IVlad

18有三个质因数——2和两个3，但只有两个不同的质因数。 - Daniel Brückner

Answer 3

这是我与 |/|ad 短暂讨论的成果 :)

read given number in n
int divisorsCount = 1;
int i;
for(i = 2; i * i < n; ++i)
{
    if(n % i == 0)
    {
        ++divisorsCount;
    }
}
divisorsCount *= 2;
if(i * i == n)
{
    ++divisorsCount;
}

- Maciej Hehl

---

是的，但你正在迭代每个数字直到 n 的平方根。我的方法有可能只迭代质数。这种方法更容易实现，但只有在你不必多次运行它时才更可取。 - IVlad

Answer 4

注意，这个答案对于单个n值不是有用/快速的。

方法1：

如果你维护一个查找表（用于一个数字的第一个质因数），那么你可以在O(polylog(n))内得到它。

如果gcd(a,b) == 1，则a*b的因子数= a的因子数 * b的因子数。

因此，对于给定的数字a*b，如果gcd(a,b) != 1，则我们可以有另外两个数字p和q，其中p = a，q = b/gcd(a,b)。因此，gcd(p,q) == 1。现在，我们可以递归地找到p和q的因子数量。

只需要花费一些小的努力来确保p和q都不是1。

P.S. 当你需要知道从1到n的所有数字的因子数量时，这种方法也很有用。它将是O(nlogn + O(查找表))的顺序。

方法2：（我不拥有此方法。）

如果你有从1到n的第一个质因数的查找表，那么你可以在O(logn)时间内知道所有的质因数，并从中找出因子的数量。

附注：请谷歌“对数级别分解”以获得更好的解释。

- Ajay

---

如果你使用Linux，你可以随时使用“factor <number>”命令来获取所有的质因数。#无需编码 - Ajay

Answer 5

欧几里得算法应该足够了。

- joejoeson

---

-1 欧几里得算法不能找到一个整数的因数分解。 - Daniel Brückner

是的。它是一个除法算法，根据定义将产生因子。也许他应该明确指定质因数分解。 - joejoeson