Problem: No of Factors of n!

Given a positive integer n, find the no of factors in n! .

Input:

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of one line. The first line of each test case consists of an integer N.

Output:

Corresponding to each test case, in a new line, print the no of factors in n!.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 100

Example:

Input
2
5
4

Output
16
8

The easy way, but only with small n ( <= 11) , Python 2.7:

from math import sqrt
from math import factorial
def factors(n):
    bound, facs = int(sqrt(n)), []
    for i in xrange(1, (bound+1)):
        if n % i == 0:
            facs.append(i)
            facs.append(n//i)
    if bound*bound == n:
        facs.append(bound)
    return set(facs)

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        res = factors(factorial(n))
        print len(res)

The hardway:
What you need?
1. You need to generate a list (or array) of primes
2. You need a function to calculate power of prime (see the code below, I commented the link where you can find the document as well as tutorial).
How’s it look like?

from math import sqrt
def make_primes(n):
    """
        generate primes <= n
    """
    sieve = [True]*(n+1)
    length = len(sieve)
    bound = int(sqrt(length))
    for i in range(2, bound+1):
        if sieve[i] == True:
            for j in range(i+i, length, i):
                sieve[j] = False
    return filter(lambda x: sieve[x] == True, range(2, length))

def power_of_prime(prime, n):
    """
        return power of prime
        watch this to know more:
        <link>https://www.youtube.com/watch?v=HkAKM2lfvAA</link>
        <link>https://www.youtube.com/watch?v=4AAavV9JBXc</link>
    """
    powers, i = [], 1
    while prime**i <= n:
        powers.append(n // (prime**i))
        i += 1
    return powers

def no_factors_of(n, primes):
    """
        return number of factors of n!
        read this to know more:
        http://math.stackexchange.com/questions/1309948/total-number-of-divisors-of-factorial-of-a-number
    """
    i, no = 0, 1
    while primes[i] <= n:
        no *= (sum(power_of_prime(primes[i], n)) + 1)
        i += 1
    return no

if __name__ == '__main__':
    """
        I made make_range(n) because
        this program is capable of solving
        n bigger than 100
    """
    t = input()
    primes = make_primes(200)
    for _ in range(t):
        n = input()
        print no_factors_of(n, primes)

 

Advertisements