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.
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).
For each test case,
1 ≤ T ≤ 100
1 ≤ N ≤ 10
2 ≤ Ai ≤ 1000000
3 5 7
2 4 6
There can be two Good Approaches to this problem:
- Use Bitwise Operators (Hybrid way)😇. Best Approach
- Use any Sieve to find Primes (Normal Way).
Let’s Code them one-by-one. In case you face any problem, feel free to comment down below. I shall be happy to help.
The Bitwise way:
This approach can be a little tricky and hard to think one the first go. But with good
- Find the number of factors the given numbers have.
- Save the number of factors in a list.
- Suppose a number has these factors -> [2, 2, 2, 3, 3, 5]
- Then the total number that can be generated from the list is given as (3+1)*(2+1)*(1+1) = 24
Our major target should be to find number of factors as quickly as possible.
import sys fac =  T = int(input()) def factors(n): count = 0 # check if a number is even and count number of 2's while n & 1 == 0: # Equivalent to //ing by 2 n >>= 1 count += 1 # append into factor list if count: fac.append((2,count)) # starting from 3 with a step of 2 till root of 'n' for i in range(3,int(n**.5)+1,2): count = 0 while n % i == 0: count += 1 n /= i if count: fac.append((i,count)) # include the last factor if n > 2: fac.append((n,1)) while T: # initialize the factor list for every test cases fac =  N = int(input()) L = list(map(int, sys.stdin.readline().split())) for i in L: factors(i) # sort the factor list for optimization fac.sort() len_factor_list = len(fac) su = 0 result = 1 num = fac i = 0 # number of factor => 12 ->[(2,2), (3,1)] --> (2+1)*(1+1) while i < len_factor_list: su = 0 while i < len_factor_list and fac[i] == num: su += fac[i] i += 1 result *= (su+1) if i < len_factor_list: num = fac[i] print(result) T -= 1
The Normal Way
import sys # get all the primes less than 1000000 def getPrime(): primes =  # initialize the array arr = *1000001 for i in range(2, 1000001): if arr[i] != 1: # set all the multiples of prime to 1 j = i * 2 while j <= 1000000: arr[j] = 1 j += i for i in range(2, len(arr)): # indexes with value zero are the primes if arr[i] == 0: primes.append(i) return primes # calculate the factors def getFactors(factors, primes, n): k = n for x in primes: # if n is divisible by x increase the value at key == x by 1 if x > k: break while n % x == 0 and n >= x: if x in factors: factors[x] += 1 else: factors[x] = 1 n /= x return factors # calculate primes primes = getPrime() t = int(sys.stdin.readline()) while t: n = int(sys.stdin.readline()) factors = dict() arr = list(map(int, sys.stdin.readline().split())) res = 1 for x in arr: factors = getFactors(factors, primes, x) for key, value in factors.items(): # number of factor => 12 ->[(2,2), (3,1)] --> (2+1)*(1+1) res *= (value + 1) print(res) t -= 1