Given an array with N elements, the task is to find the count of factors of a number X which is product of all array elements. 
 
Example 1:
Input:
N = 3
Arr[] = {2, 4, 6}
Output:
10
Explanation:
2 * 4 * 6 = 48, the factors of 48 are 
1, 2, 3, 4, 6, 8, 12, 16, 24, 48
whose count is 10.
 
Example 2:
Input:
N = 3
Arr[] = {3, 5, 7}
Output:
8
Explanation:
3 * 5 * 7 = 105, the factors of 105 are 
1, 3, 5, 7, 15, 21, 35, 105 whose count is 8.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countDivisorsMult() which takes the array A[] and its size N as inputs and returns the count of factors of X.
 
Expected Time Complexity: O(N. sqrt(N))
Expected Auxiliary Space: O(N)
 
Constraints:
2<=N<=10^{2}
1<=Arr[i]<=10^{2}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

Starter code: #User function Template for python3



class Solution:

    def countDivisorsMult(self, a, n):

        #Code here

    

    

    

    



Solutions:
from math import sqrt

class Solution:

	def countDivisorsMult(self, a, n):
		prime_freq = {}
		for i in range(n):
			x = a[i]
			j = 2
			while j * j <= x:
				while x % j == 0:
					prime_freq[j] = prime_freq.get(j, 0) + 1
					x //= j
				j += 1
			if x > 1:
				prime_freq[x] = prime_freq.get(x, 0) + 1
		count = 1
		for freq in prime_freq.values():
			count *= freq + 1
		return count


def primefactors(n, freq):
	while n % 2 == 0:
		if 2 not in freq:
			freq[2] = 0
		freq[2] += 1
		n //= 2
	for i in range(3, int(n ** (1 / 2)) + 1, 2):
		while n % i == 0:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
			n //= i
	if n > 2:
		if n not in freq:
			freq[n] = 0
		freq[n] += 1

class Solution:

	def countDivisorsMult(self, a, n):
		freq = {}
		for i in a:
			primefactors(i, freq)
		p = 1
		for i in freq:
			p *= freq[i] + 1
		return p


class Solution:

	def countDivisorsMult(self, a, n):
		prod = 1
		for i in range(len(a)):
			prod *= a[i]
		p = 2
		prime = []
		while prod != 1:
			if prod % p == 0:
				prod //= p
				prime.append(p)
				continue
			p += 1
		d = {i: prime.count(i) for i in prime}
		No_of_factors = 1
		for (key, value) in d.items():
			No_of_factors *= 1 + value
		return No_of_factors


from math import sqrt

class Solution:
	s = 1

	def factors(self, n):
		c = 2
		d = {}
		while n > 1:
			if n % c == 0:
				d[c] = d.get(c, 0) + 1
				n = n // c
			else:
				c += 1
		for i in d.keys():
			self.s = self.s * (d[i] + 1)

	def countDivisorsMult(self, a, n):
		m = 1
		for i in a:
			m = m * i
		self.factors(m)
		return self.s


class Solution:

	def countDivisorsMult(self, a, n):
		M = 104
		primes = [1 for i in range(105)]
		for i in range(2, M + 1):
			for j in range(2 * i, M + 1, i):
				primes[j] = 0
		primes[1] = 0
		primes[0] = 0
		final = []
		for i in range(M + 1):
			if primes[i] == 1:
				final.append(i)
		from collections import defaultdict
		d = defaultdict(int)
		for x in a:
			for i in final:
				while x % i == 0:
					d[i] += 1
					x = x // i
		ans = 1
		for i in d:
			ans *= d[i] + 1
		return ans


class Solution:

	def countDivisorsMult(self, arr, n):
		ans = 1
		mp = {}
		for i in range(n):
			j = 2
			while j * j <= arr[i] and arr[i] > 1:
				cnt = 0
				while arr[i] % j == 0:
					arr[i] = arr[i] // j
					cnt += 1
				if mp.__contains__(j):
					mp[j] += cnt
				else:
					mp[j] = cnt
				j += 1
			if arr[i] > 1:
				if mp.__contains__(arr[i]):
					mp[arr[i]] += 1
				else:
					mp[arr[i]] = 1
		for key in mp:
			ans *= mp[key] + 1
		return ans


import numpy

class Solution:

	def countDivisorsMult(self, a, n):
		prod = 1
		for i in a:
			prod *= i
		p = 2
		prime = {}
		while prod != 1:
			if prod % p == 0:
				prod //= p
				if p not in prime:
					prime[p] = 1
				else:
					prime[p] += 1
				continue
			p += 1
		No_of_factors = 1
		for (key, value) in prime.items():
			No_of_factors *= 1 + value
		return No_of_factors


import math
from collections import defaultdict

class Solution:

	def checkprimebysieve(self, largest, prime):
		isPrime = [True] * (largest + 1)
		p = 2
		while p * p <= largest:
			if isPrime[p] == True:
				for i in range(p * 2, largest + 1, p):
					isPrime[i] = False
			p += 1
		for p in range(2, largest + 1):
			if isPrime[p]:
				prime.append(p)

	def countDivisorsMult(self, a, n):
		largest = max(a)
		prime = []
		self.checkprimebysieve(largest, prime)
		mp = defaultdict(int)
		for i in range(n):
			for j in range(len(prime)):
				while a[i] > 1 and a[i] % prime[j] == 0:
					a[i] //= prime[j]
					mp[prime[j]] += 1
			if a[i] != 1:
				mp[a[i]] += 1
		res = 1
		for it in mp.values():
			res *= it + 1
		return res


import math
from collections import Counter

class Solution:

	def countDivisorsMult(self, a, n):
		p = 1
		c = 0
		for i in range(len(a)):
			p = p * a[i]
		c = 2
		u = []
		while p > 1:
			if p % c == 0:
				u.append(c)
				p = p // c
			else:
				c = c + 1
		s = Counter(u)
		v = 1
		for (x, y) in s.items():
			v = v * (y + 1)
		return v


import math

class Solution:

	def seive(self, n):
		ans = [i for i in range(n + 1)]
		ans[0] = 0
		ans[1] = 0
		p = 2
		while p ** 2 < n + 1:
			for i in range(p * 2, n + 1, p):
				ans[i] = 0
			p += 1
		new = []
		for i in ans:
			if i != 0:
				new.append(i)
		return new

	def prime(self, n):
		if n == 0 or n == 1:
			return True
		else:
			for i in range(2, int(math.sqrt(n) + 1)):
				if n % i == 0:
					return False
			return True

	def countDivisorsMult(self, a, n):
		maxi = max(a)
		primes = self.seive(maxi)
		d = {}
		for i in range(n):
			if a[i] == 1:
				continue
			if self.prime(a[i]):
				if a[i] not in d:
					d[a[i]] = 1
				else:
					d[a[i]] += 1
			else:
				try:
					j = 0
					while a[i] != 1:
						cnt = 0
						curr = primes[j]
						while a[i] % curr == 0:
							cnt += 1
							a[i] = a[i] // curr
						if curr not in d:
							d[curr] = cnt
						else:
							d[curr] += cnt
						j += 1
				except:
					return a[i]
		ans = 1
		for value in d.values():
			if value != 0:
				ans *= value + 1
		return ans


class Solution:

	def countDivisorsMult(self, a, n):
		prod = 1
		for i in a:
			prod *= i
		p = 2
		prime = {}
		while prod != 1:
			if prod % p == 0:
				prod //= p
				if p not in prime:
					prime[p] = 1
				else:
					prime[p] += 1
				continue
			p += 1
		No_of_factors = 1
		for (key, value) in prime.items():
			No_of_factors *= 1 + value
		return No_of_factors

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(Solution().countDivisorsMult(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def countDivisorsMult(self, a, n):
		prod = 1
		ans = 0
		for i in a:
			prod *= i
		div = 2
		prime = {}
		while prod != 1:
			if prod % div == 0:
				prod = prod // div
				if div not in prime:
					prime[div] = 1
				else:
					prime[div] += 1
				continue
			div += 1
		ans = 1
		for (k, v) in prime.items():
			ans *= v + 1
		return ans

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(Solution().countDivisorsMult(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def countDivisorsMult(self, a, n):
		prod = 1
		for i in range(len(a)):
			prod *= a[i]
		p = 2
		prime = []
		while prod != 1:
			if prod % p == 0:
				prod //= p
				prime.append(p)
				continue
			p += 1
		d = {i: prime.count(i) for i in prime}
		No_of_factors = 1
		for (key, value) in d.items():
			No_of_factors *= 1 + value
		return No_of_factors

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(Solution().countDivisorsMult(a, n))
		T -= 1
if __name__ == '__main__':
	main()


import math

class Solution:

	def countDivisorsMult(self, a, n):
		mul = 1
		count = 0
		for i in a:
			mul = mul * i
		pro = 2
		ans = []
		while mul != 1:
			if mul % pro == 0:
				mul = mul // pro
				ans.append(pro)
				continue
			pro = pro + 1
		temp = {i: ans.count(i) for i in ans}
		fact = 1
		for (a, b) in temp.items():
			fact = fact * (1 + b)
		return fact


class Solution:

	def countDivisorsMult(self, a, n):

		def count(n):
			i = 2
			d = {}
			while i * i <= n:
				while n % i == 0:
					n //= i
					try:
						d[i] += 1
					except:
						d[i] = 1
				i += 1
			if n > 1:
				d[n] = 1
			return d
		prod = 1
		for i in a:
			prod *= i
		factorsMap = count(prod)
		countOfDivisors = 1
		for i in factorsMap.values():
			countOfDivisors *= i + 1
		return countOfDivisors


from collections import defaultdict

class Solution:

	def countDivisorsMult(self, a, n):
		ma = max(a)
		prime = []
		p = 0
		d = defaultdict(int)
		for i in range(1, ma):
			if i == 2:
				p += 1
				prime.append(2)
			elif i == 3:
				p += 1
				prime.append(3)
			elif i == 5:
				p += 1
				prime.append(5)
			elif i == 7:
				p += 1
				prime.append(7)
			if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0) and (i % 7 != 0) and (i > 10):
				p += 1
				prime.append(i)
		for i in range(0, n):
			for j in range(0, p):
				while a[i] > 1 and a[i] % prime[j] == 0:
					a[i] = a[i] // prime[j]
					d[prime[j]] += 1
			if a[i] != 1:
				d[a[i]] += 1
		res = 1
		for i in d.values():
			res *= i + 1
		return res