How to find Number of Factors of "product of numbers"

Question

I m trying to find number of factors of product of big numbers.

The problem statement is this : Suppose you are given N numbers(let say N = 10), each number <= 1000000. How to find the number of factors of the product of such numbers.

Can someone please provide an efficient algorithm for doing this.

Example :

1) N = 3 and Numbers are 3, 5, 7

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

2) N = 2 and Numbers are 5, 5

Ans = 3 (1, 5 and 25)

Answer 1

Editorial for the problem is here

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

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);
}

This got Accepted.

Sample Inputs and Outputs:

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