NUMFACT - Number of Factors

This problem is from Codechef Medium Practice Problems (NUMFACT)

I received the Most Captivating Creator award in the CodeChef Creator Hunt for my video explanation of this problem

Problem

Alice has learnt factorization recently. Bob doesn’t think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of \(N\) numbers. Alice is frightened of big numbers, you need to tell the number of distinct factors of the product of these \(N\) numbers.

Input

First line of input contains a single integer \(T\) \((1 \leq T \leq 100)\), the number of test cases.

Each test starts with a line containing a single integer \(N\) \((1 \leq N \leq 10)\).

The next line consists of \(N\) space separated integers \(A_i\) \((2 \leq A_i \leq 1000000)\).

Output

For each test case, output on a separate line the total number of factors of the product of given numbers.

Example

Input

3
3
3 5 7
3
2 4 6
2
5 5

Output

8
10
3

Solution

If we define the product of the \(N\) space separated integers as \(X\), a naive approach would be to check whether each integer from \(1\) to \(X\) is a factor of \(X\) and counting those that are. Even optimizing it further and checking from \(1\) to \(\sqrt{X}\) instead and counting each factor pair is not enough to make a solution that doesn’t exceed the time limit.

Idea

All the factors of \(X\) are just its prime factors raised to different powers. For example when the input is \(3, 5, 7\), the product \((X)\) would be \(105\). Note, it is not always the case that the input is the same as the prime factors.

Therefore, to find the total number of factors, compute the number of possible combinations of the prime factors raised from \(0\) up to the highest exponent. In this case, \(3\) can be raised from \(0\) to \(1\), \(5\) can be raised from \(0\) to \(1\), and \(7\) can be raised from \(0\) to \(1\) so the total number of combinations and hence the total number of factors are \(2 \times 2 \times 2 = 8\). Remember that it is \(2\) not \(1\) because we include \(0\) as a potential exponent.

My Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1000001;
vector<int> primes;

void sieve() {
	bool isPrime[N];
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i < N; i++) isPrime[i] = true;
	for (int i = 2; i < N; i++) {
		if (isPrime[i]) for (int j = 2; i * j < N; j++) {
			isPrime[i*j] = false;
		}
	}
	for (int i = 0; i < N; i++) if (isPrime[i]) primes.push_back(i);
}
void pFactorise(int n, map<int, int> &pFactors) {
	for (int p : primes) {
		if (n % p == 0) {
			while (n % p == 0) {
				n /= p;
				pFactors[p]++;
			}
		}
	}
}

int main() {
  sieve();
	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		int n; cin >> n;
		map<int, int> pFactors;
		for (int j = 0; j < n; j++) {
			int x; cin >> x;
			pFactorise(x, pFactors);
		}
		int res = 1;
		for (auto j : pFactors) {
			res *= j.second + 1;
		}
		cout << res << endl;
	}

	return 0;
}

If you have any corrections, suggestions, or feedback, please feel free to email them to beaux@codesunji.com. I’d love to hear back from you and improve this site in any way I can :]