Categories: CodeChef's Solutions

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


Output

For each test case, output on a separate line the total number of factors of the product of given numbers.

Related Post

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

Aditya Kumar

Share
Tags: CodeChef Python

Recent Posts

  • Programming

Mastering Print Formatting in Python: A Comprehensive Guide

In Python, the print() function is a fundamental tool for displaying output. While printing simple…

8 months ago
  • Programming

Global Variables in Python: Understanding Usage and Best Practices

Python is a versatile programming language known for its simplicity and flexibility. When working on…

8 months ago
  • Programming

Secure Your Documents: Encrypting PDF Files Using Python

PDF (Portable Document Format) files are commonly used for sharing documents due to their consistent…

8 months ago
  • Programming

Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

PDF (Portable Document Format) files are widely used for document exchange due to their consistent…

8 months ago
  • Programming

Boosting Python Performance with Cython: Optimizing Prime Number Detection

Python is a high-level programming language known for its simplicity and ease of use. However,…

8 months ago
  • Programming

Using OOP, Iterator, Generator, and Closure in Python to implement common design patterns

Object-Oriented Programming (OOP), iterators, generators, and closures are powerful concepts in Python that can be…

8 months ago

This website uses cookies.