c - 如何找到“数字乘积”的因子数

Question

我正在尝试查找大数乘积的因子数。

问题陈述是这样的：假设你有 N 个数字（假设 N = 10），每个数字 <= 1000000。如何找到这些数字乘积的因子数。

有人可以提供一个有效的算法来做到这一点。

例子 ：

1) N = 3，数字为 3、5、7

答案 = 8 (1, 3, 5, 7, 15, 21, 35, 105)

2) N = 2，数字为 5, 5

答案 = 3（1、5 和 25）

Answer 1

问题的编辑在这里

http://discuss.codechef.com/questions/15943/numfact-editor

int total = 0, N = 0, Number;
scanf ("%d", &total);
while (total--)
{
    scanf ("%d", &N);
    map<int, int> Counter;
    for (int i = 0; i < N; i++)
    {
        scanf ("%d", &Number);
        for (int j = 2; j * j <= Number; j++)
        {
            while (Number % j == 0)
            {
                Counter[j]++;
                Number /= j;
            }
        }
        if (Number > 1) Counter[Number]++;
    }
    int Answer = 1;
    for (map<int, int>::iterator it = Counter.begin(); it != Counter.end(); it++)
        Answer *= (it->second + 1);
    printf ("%d\n", Answer);
}

这被接受了。

示例输入和输出：

7
3
3 5 7
3
2 4 6
2
5 5
10
2 2 2 2 2 2 2 2 2 2 
1
100
10
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 

8
10
3
11
9
1681
3721

Answer 2

L(n) = { p_i , k_i }对于一个数n = Π p _i ^{k _i}，将每个数分解为素数及其重数的列表。这样的n的除数数量是 ND( L(n) ) = Π (k _i +1) 所有系数的乘积，每个系数增加 1（这包括 1 和n本身作为 n 的除数）。这对应于从它们中的每一个中选择none, one, ... k _i来相乘。

要计算任意数量的数字乘积的 ND，请将每个数字分解并合并它们的分解，在匹配素数的情况下，它们的系数被加在一起。然后计算合并分解的ND。

要将许多分解合并在一起，首先要合并其中的两个；然后合并结果和下一个；然后合并最后一个结果和下一个因式分解，依此类推。这称为折叠。或者最好将它们成对合并，然后以相同的成对方式合并结果，依此类推，只剩下一个合并结果。这类似于自下而上的归并排序。

Answer 3

将所有数字相乘，分解结果，计算所有除数：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
    int p = 1;
    for (int i = 1; i < argc; i++)
        p *= strtol(argv[i], NULL, 10);

    int n = 0;
    int s = sqrt(p) + 1;
    for (int i = 1; i <= s; i++)
        if (p % i == 0)
            n += 2 - (p / i == i); // obfuscation ;)

    printf("%d\n", n);
    return 0;
}