Top 10 Programming Languages to Learn in 2019

CodeChef's Solutions

# Number of Factors Solution with Approach – CodeChef Page Contents

## 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 (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 `

## 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:

#### 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())
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

#### Code

```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()
while t:
factors = dict()
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```