# Number of Factors | codechef solution

## 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 and hence is asking you for help. Your task is simple. Given N 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, the number of test cases.
• Each test starts with a line containing a single integer N.
• The next line consists of N space separated integers (Ai).

### Output:

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

### Constraints:

```1 ≤ T ≤ 100
1 ≤ N ≤ 10
2 ≤ Ai ≤ 1000000
```

### Scoring:

• You will be awarded 40 points for correctly solving for Ai ≤ 100.
• You will be awarded another 30 points for correctly solving for Ai ≤ 10000.
• The remaining 30 points will be awarded for correctly solving for Ai ≤ 1000000.

### Sample 1:

Input
Output
```3
3
3 5 7
3
2 4 6
2
5 5```
```8
10
3```

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long int mod = 1e9+7;
const int N = 1e6+3;
vector<bool>prime(N, 1);
vector<ll>lp(N), hp(N);

int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
prime[0] = prime[1] = false;
for(int i = 2; i<N; i++)
{
if(prime[i] == true)
{
lp[i] = hp[i] = i;
for(int j = 2*i; j<N; j+=i)
{
prime[j] = false;
hp[j] = i;
if(lp[j] == 0)
{
lp[j] = i;
}
}
}
}
ll t;
cin>>t;
while(t--)
{
ll n, ans;
cin>>n;
map<ll, ll>mp;
for(int i = 0; i<n; i++)
{
cin>>ans;
while(ans > 1)
{
ll high = lp[ans];
ans /= high;
mp[high]++;
}
}

ll val = 1;
for(auto it : mp)
{
val = val*(it.second+1);
}
cout<<val<<endl;
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
int N = (int)Math.ceil(Math.sqrt(1_000_000));
boolean[] visited = new boolean[N];
List<Integer> list = new ArrayList<>();
for(int i=2;i<N;i++){
if(!visited[i]){
for(int j=i;j<N;j+=i) visited[j] = true;
}
}
//      System.out.println(list);
for(int testCase=1;testCase<=testCases;testCase++){
int n = sc.nextInt();
Map<Integer,Integer> freq = new HashMap<>();
for(int i=0;i<n;i++){
int num = sc.nextInt();
for(int p: list){
int cnt = 0;
while(num%p == 0){
cnt++;
num /= p;
}
if(cnt>0) freq.put(p,freq.getOrDefault(p,0)+cnt);
}
if(num>=N) freq.put(num,freq.getOrDefault(num,0)+1);
}
//       System.out.println(freq);
long res = 1;
for(int k: freq.keySet()){
res *= (freq.get(k)+1);
}
System.out.println(res);
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-