Number of Factors | CodeChef Solution

Hello coders, today we are going to solve Number of Factors CodeChef Solution whose Problem Code is NUMFACT.

Task

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 Format

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 (A_i).

Output Format

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 ≤ A_i ≤ 1000000

Example

Sample Input

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

Sample Output

8
10
3

Scoring

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

Solution – Number of Factors

C++

#include <bits/stdc++.h>
#define N 1000001
using namespace std;

vector<bool>Primes(N, true);
vector<int>primes;

void init(){
    for(int i = 2; i*i <=N; i++){
        for(int j = i*i; j<=N; j+= i){
            Primes[j] = false;
        }
    }
    
    Primes[1] = Primes[0] = false;
    for(int i = 2; i<N; i++){
        if(Primes[i])
            primes.push_back(i);
    }
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    init();
    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        int div[n];
        for(auto&it:div)
            cin>>it;
        
        unordered_map<int, int>mp;
        for(auto&it:div){
            
            if(Primes[it] == true){
                mp[it]++;
            }
            else
            {
                
                for(int i = 2; i<it; i++){
                    if( it%i == 0){
                        int temp = it;
                        if(Primes[i]){
                            while(temp%i == 0){
                                temp = temp/i;
                                mp[i]++;
                            }
                        }
                        
                        
                    }
                }
            }
            
        }
        long long ans = 1;
        for(auto&it:mp){
            ans *= (it.second + 1);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Python

import math
from collections import Counter
try:
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int,input().split()))
        l2 = []
        for num in arr:
            for i in range(2,int(num**0.5)+1):
                while num%i == 0:
                    l2.append(i)
                    num//=i
            if num>1:
                l2.append(num)
        c = Counter(l2)
        ans = 1
        for i in c:
            ans *= (c[i]+1)
        print(ans)
except:
    pass

Java

import java.util.Scanner;
		
class findfactors {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			int n = sc.nextInt();
			int N = 1;
			int[] data = new int[1000001];
			for (int j = 0; j < n; j++) {
				int k = sc.nextInt();
				data= factors(k, data);
				/*System.out.print(k + ": ");
				for(int m = 0;m<data.length;m++) {
					if(data[m]!=0) {
						//N*=(data[m]+1);
						System.out.print(m + "-> "+ data[m]+";  ");
					}
				}System.out.println(" ");*/
			}
			
			for(int m = 0;m<data.length;m++) {
				if(data[m]!=0) {
					N*=(data[m]+1);
					//System.out.print(m + "-> "+ data[m]+";  ");
				}
			}
			System.out.println(N);
			//1System.out.println(factors(N));
		}	
	}

	private static int[] factors(int n, int[] data) {		
		int ny = n;
		long r = (long)Math.sqrt(n);
		for (int i = 1; i <= r+1; i++) {
			//System.out.println("===");
			if(n%i == 0) {
				while(isPrime(i)&&ny%i==0) {
					data[i]++;
					ny = ny/i;
				}
				while(isPrime(n/i)&& ny%(n/i)==0) {
					data[n/i]++;
					ny = ny/(n/i);
				}				
			}
		}
		
		return data;
	}
	private static boolean isPrime(int i) {
		boolean isprime = true;
		if(i==1) {
			isprime=false;
		}
		for(long i1 = 2;i1<=Math.sqrt(i);i1++ ) {
			if(i%i1==0) {
				isprime = false;
				break;
			}
		}
		return isprime;
	}
}		

Disclaimer: The above Problem (Number of Factors) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.