Number of Factors Solution with Approach – CodeChef

Problem Statement

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

---

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 

---

Example

Input:
3 
3 
3 5 7 
3 
2 4 6 
2 
5 5 

Output:
8 
10 
3 

---

Solution

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 practice this can make your life easy. Want to know more about bitwise operators. Check out this tutorial:

• Bitwise Operators in Python

Approach

• 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.

Code

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[0][0]
    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][0] == num:
            su += fac[i][1]
            i += 1
        result *= (su+1)
        if i < len_factor_list:
            num = fac[i][0]
    print(result)
    T -= 1

---

The Normal Way

Code

import sys


# get all the primes less than 1000000
def getPrime():
    primes = []
    # initialize the array
    arr = [0]*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

---