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

## Reply