Problem:
 Score : 400 points    Problem Statement You are given an integer N . Among the divisors of N!  (= 1 \times 2 \times ... \times N) , how many Shichi-Go numbers (literally "Seven-Five numbers") are there?  Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.      Note When a positive integer A divides a positive integer B , A is said to a divisor of B .
For example, 6 has four divisors: 1, 2, 3 and 6 .      Constraints  1 \leq N \leq 100  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the number of the Shichi-Go numbers that are divisors of N! .        Sample Input 1 9      Sample Output 1 0  There are no Shichi-Go numbers among the divisors of 9! = 1 \times 2 \times ... \times 9 = 362880 .       Sample Input 2 10      Sample Output 2 1  There is one Shichi-Go number among the divisors of 10! = 3628800 : 32400 .       Sample Input 3 100      Sample Output 3 543

Solution (Python):
from collections import defaultdict as dd
N = int(input())





primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
ct = dd(int)
for i in range(1, N+1):
  for j in primes:
    x = i
    while x % j == 0:
      ct[j] += 1
      x //= j

over74 = []
over24 = []
over14 = []
over4 = []
over2 = []
for k, v in ct.items():
  if v >= 74:
    over74.append(k)
  elif v >= 24:
    over24.append(k)
  elif v >= 14:
    over14.append(k)
  elif v >= 4:
    over4.append(k)
  elif v >= 2:
    over2.append(k)

l2 = len(over2)
l4 = len(over4)
l14 = len(over14)
l24 = len(over24)
l74 = len(over74)
print(
  l2 * (l4+l14+l24+l74) * ((l4+l14+l24+l74) - 1) // 2 +
  (l4+l14+l24+l74) * ((l4+l14+l24+l74) - 1) * ((l4+l14+l24+l74) - 2) // 2 +
  l4 * (l14+l24+l74) +
  (l14+l24+l74) * ((l14+l24+l74) - 1) +
  (l2+l4+l14) * (l24+l74) +
  (l24+l74) * ((l24+l74) - 1) +
  l74
)

Solution (Python):
N = int(input())
lim = 1
for i in range(N): lim *= (i+1)
Prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,\
    53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Ans = 0
for i in range(23):
    for j in range(i+1, 24):
        for k in range(j+1, 25):
            a, b, c = Prime[i], Prime[j], Prime[k]
            d, e, f = (a**4)*(b**4)*(c**2), (a**4)*(b**2)*(c**4), (a**2)*(b**4)*(c**4)
            if d <= lim and lim%d == 0: Ans += 1
            if e <= lim and lim%e == 0: Ans += 1
            if f <= lim and lim%f == 0: Ans += 1
for i in range(24):
    for j in range(i+1, 25):
        a, b = Prime[i], Prime[j]
        d, e, f, g = (a**24)*(b**2), (a**2)*(b**24), (a**4)*(b**14), (a**14)*(b**4)
        if d <= lim and lim%d == 0: Ans += 1
        if e <= lim and lim%e == 0: Ans += 1
        if f <= lim and lim%f == 0: Ans += 1
        if g <= lim and lim%g == 0: Ans += 1
for i in range(5):
    if Prime[i] ** 74 <= lim and lim % (Prime[i]**74) == 0: Ans += 1
print(Ans)

Solution (Python):
N = int(input())
from math import ceil, sqrt, factorial
from itertools import permutations
def eratosthenes(n):
    l = [1 for i in range(n+1)]
    l[0] = l[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if l[i] == 0: continue
        for j in range(i*2, n+1, i):
            l[j] = 0
    return l

m = factorial(N)
ans = set()

p = eratosthenes(530)

p = [i for i,v in enumerate(p) if v ]

for i in p:
    a = i**74
    if not m % a:
        ans.add(a)
        break

for a,b in permutations(p,2):
    c = a**2*b**24
    if not m % c:
        ans.add(c)
    c = a**4*b**14
    if not m % c:
        ans.add(c)

for a,b,c in permutations(p, 3):
    d = a**2 * b**4 * c ** 4
    if not m % d:
        ans.add(d)

print(len(ans))

Solution (Python):
n = int(input())
x = 1
for i in range(1,n+1):
    x *=i

def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

a = factorize(x)
prime= []
num = []
for s in a:
    if s[1]>1:
        prime.append(s[0])
        num.append(s[1])
ans = 0
ab24 = []
ab14 = []
ab4 = []
alls = []
for n,p in zip(num,prime):
    if n>=74:
        ans += 1
    if n>=24:
        ab24.append([p,n])
    if n>=14:
        ab14.append([p,n])
    if n>=4:
        ab4.append([p,n])
    alls.append([p,n])

ans += len(ab24)*(len(alls)-len(ab24)) + len(ab24)*(len(ab24)-1)
ans += len(ab14)*(len(ab4)-len(ab14)) + len(ab14)*(len(ab14)-1)
ans += len(ab4)*(len(ab4)-1)*(len(alls)-2)/2
print(int(ans))

Solution (Python):
N = int(input())
from math import ceil, sqrt, factorial
from itertools import permutations
def eratosthenes(n):
    l = [1 for i in range(n+1)]
    l[0] = l[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if l[i] == 0: continue
        for j in range(i*2, n+1, i):
            l[j] = 0
    return l

m = factorial(N)
ans = set()

p = eratosthenes(530)

p = [i for i,v in enumerate(p) if v ]

for i in p:
    a = i**74
    if not m % a:
        ans.add(a)
        break

for a,b in permutations(p,2):
    c = a**2*b**24
    if not m % c:
        ans.add(c)
    c = a**4*b**14
    if not m % c:
        ans.add(c)

for a,b,c in permutations(p, 3):
    d = a**2 * b**4 * c ** 4
    if not m % d:
        ans.add(d)

print(len(ans))

Solution (Python):
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

n = getN()
def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

yaku = []
for i in range(2,n+1):
    yaku = yaku + (primes(i))


from collections import defaultdict
yakunum = defaultdict(int)
for i in yaku:
    yakunum[i] += 1


over2, over4, over14, over24, over74 = 0,0,0,0,0
for i in yakunum.values():

    if i > 1:
        over2 += 1
    if i > 3:
        over4 += 1
    if i > 13:
        over14 += 1
    if i > 23:
        over24 += 1
    if i > 73:
        over74 += 1


ans = over74 + (over24*over2)-(over24) + (over14*over4)-over14 + ((over4)*(over4-1)*(over2-2))//2

print(ans)

Solution (Python):
import math
from collections import defaultdict

n = int(input())
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0  

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
pr = primes(100)
q = math.factorial(n)
di = {}
di = defaultdict(int)
for i in pr:
    while q % i == 0:
        q = q // i
        di[i] += 1
co = 0
do1 = 0
eo1= 0
do2 = 0
eo2= 0
do3 = 0
eo3= 0
for k in di:
    if di[k] >= 24:
        do1 += 1
    if di[k] >= 2:
        eo1 += 1
if do1 >= 1 and eo1 >= 2:
    co += do1 * (eo1 - 1)
for k in di:
    if di[k] >= 14:
        do2 += 1
    if di[k] >= 4:
        eo2 += 1
if do2 >= 1 and eo2 >= 2:
    co += do2 * (eo2 - 1)
for k in di:
    if di[k] >= 4:
        do3 += 1
    if di[k] >= 2:
        eo3 += 1
if do3 >= 2 and eo3 >= 3:
    co += comb(do3,2) * (eo3 - 2)
for k in di:
    if di[k] >= 74:
        co += 1
print(co)

Solution (Python):
import itertools

N = int(input())
b = [False] * 101
prime = []
b[1] = True

for i in range(2, 101):
    if b[i]:
        continue
    k = i + i
    while k < 101:
        b[k] = True
        k += i

    prime.append(i)

p = [[0] * len(prime) for i in range(N + 1)]

for i in range(1, N + 1):
    n = i
    for j in range(len(prime)):
        while n % prime[j] == 0:
            p[i][j] += 1
            n //= prime[j]

pp = [0] * len(prime)

for i in range(len(prime)):
    for j in range(1, N + 1):
        pp[i] += p[j][i]

ans = 0

for x in pp:
    if x >= 74:
        ans += 1

for a in list(itertools.combinations(range(len(prime)), 2)):
    if pp[a[0]] >= 24 and pp[a[1]] >= 2:
        ans += 1
    if pp[a[0]] >= 2 and pp[a[1]] >= 24:
        ans += 1
    if pp[a[0]] >= 14 and pp[a[1]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 14:
        ans += 1

for a in list(itertools.combinations(range(len(prime)), 3)):
    if pp[a[0]] >= 2 and pp[a[1]] >= 4 and pp[a[2]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 2 and pp[a[2]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 4 and pp[a[2]] >= 2:
        ans += 1

print(ans)

Solution (Python):
from itertools import takewhile


def prime_cnt(x):
    y = x
    ret = 0
    while y <= n:
        z = y
        while True:
            ret += 1
            z //= x
            if z == 0 or z % x:
                break
        y += x
    return ret


n = int(input())
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
pc = list(map(prime_cnt, ps))

l2 = len(list(takewhile(lambda x: x >= 2, pc)))
l4 = len(list(takewhile(lambda x: x >= 4, pc)))
l14 = len(list(takewhile(lambda x: x >= 14, pc)))
l24 = len(list(takewhile(lambda x: x >= 24, pc)))
l74 = len(list(takewhile(lambda x: x >= 74, pc)))
ans = l4 * max(0, l4 - 1) * max(0, l2 - 2) // 2
ans += l14 * max(0, l4 - 1)
ans += l24 * max(0, l2 - 1)
ans += l74

print(ans)

Solution (Python):
def is_prime(i):
  if i < 2:
    return False
  for j in range(2, i):
    if i % j == 0:
      return False
  return True
primes = [i for i in range(100) if is_prime(i)]

n = int(input())
dic = {}
for i in primes:
  dic[i] = 0

def soinsuubunnkai(x, dic):
  while True:
    for i in primes:
      if x % i == 0:
        dic[i] += 1
        x //= i
        break
    else:
      break

for i in range(1, n + 1):
  soinsuubunnkai(i, dic)

s75 = len([i for i in list(dic.values()) if i >= 74])
s25 = len([i for i in list(dic.values()) if i >= 24])
s15 = len([i for i in list(dic.values()) if i >= 14])
s5 = len([i for i in list(dic.values()) if i >= 4])
s3 = len([i for i in list(dic.values()) if i >= 2])
ans = 0
ans += s75
ans += s25 * (s3 - 1)
ans += s15 * (s5 - 1)
ans += (s5 * (s5 - 1)) // 2 * (s3 - 2)
print(ans)

Solution (Python):

from collections import defaultdict
def inpl(): return list(map(int, input().split()))

N = int(input())
P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
X = [0]*25
for i in range(1, N+1):
    for j in range(25):
        while i % P[j] == 0:
            i = i//P[j]
            X[j] += 1

ans = 0

for i in range(25):
    if X[i] >= 74:
        ans += 1

over = defaultdict(set)
for i in range(25):
    for j in [2, 4, 14, 24]:
        if X[i] >= j:
            over[j].add(i)

for o2 in over[2]:
    o4 = over[4] - set([o2])
    o24 = over[24] - set([o2])
    ans += len(o4) * (len(o4)-1) // 2
    ans += len(o24)

for o4 in over[4]:
    o14 = over[14] - set([o4])
    ans += len(o14)

print(ans)

Solution (Python):
N=int(input())
L={}
cnt = 0
for i in range(2, N+1):
    X=i
    f = 0
    while f == 0:
        for j in range(2, X+1):
            if X % j == 0:
                if j in L:
                    L[j]=L[j]+1
                else:
                    L[j]=1
                X=int(X/j)
                if X==1:
                    f = 1
                break

C75 = 0
C25 = 0
C15 = 0
C5 = 0
C3 = 0
for i in L.values():
    if i >= 74:
        C75 += 1
    if i >= 24:
        C25 += 1
    if i >= 14:
        C15 += 1
    if i >= 4:
        C5 += 1
    if i >= 2:
        C3 += 1
cnt = C75
cnt += C25 * (C3-1)
cnt += C15 * (C5-1)
cnt += int(C5 * (C5-1) / 2 * (C3-2))
print(cnt)

Solution (Python):
n = int(input())
factor = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
factor_num = [0] * len(factor)
if n <= 9:
	print(0)
else:
	for i in range(2, n+1):
		for j in range(len(factor)):
			cnt = 0
			while i % factor[j] == 0:
				cnt += 1
				i = i // factor[j]
			factor_num[j] += cnt

	two_three = 0
	over_four = 0
	over_fourteen = 0
	over_twentyfour = 0
	over_seventyfour = 0

	for i in range(len(factor)):
		if 2 <= factor_num[i] <= 3:
			two_three += 1
		elif factor_num[i] >= 4:
			over_four += 1
			if factor_num[i] >= 14:
				over_fourteen += 1
			if factor_num[i] >= 24:
				over_twentyfour += 1
			if factor_num[i] >= 74:
				over_seventyfour += 1

	ans = two_three * (over_four * (over_four - 1) // 2) + over_four * ((over_four - 1) * (over_four - 2) // 2)
	ans += over_fourteen * (over_four - 1) + over_twentyfour * (two_three + over_four - 1)
	ans += over_seventyfour

	print(ans)

Solution (Python):
import types, math, operator
import numpy as np
from math import sqrt
from collections import Counter
from itertools import product
from functools import reduce
class PrimeUtils:
    @staticmethod
    def _has_numpy():
        g = globals()
        m = g.get('np')
        if m is not None and isinstance(m, types.ModuleType):
            return  m.__name__ == 'numpy'
        return False
    @staticmethod
    def _primes_sieve_pp(n):
        sieve = [True] * (n + 1)
        for i in range(2, int(sqrt(n)) + 1):
            if sieve[i]:
                for j in range(i * i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    def _primes_sieve_np(n):
        sieve = np.ones(n + 1, np.bool)
        sieve[0] = sieve[1] = False
        for i, v in enumerate(sieve[2:int(sqrt(n)) + 1], 2):
            if v: sieve[i*i::i] = False
        return np.nonzero(sieve)[0]
    @staticmethod
    def _primes_sieve_np_fast(n):
        n += 1
        sieve = np.ones(n//3 + (n%6 == 2), dtype=np.bool)
        check_upper = int(sqrt(n)) // 3
        for i, v in enumerate(sieve[1:check_upper + 1], 1):
            if v:
                k = (3*i + 1) | 1
                sieve[k* k           //3::2*k] = False
                sieve[k*(k-2*(i&1)+4)//3::2*k] = False
        sieve[0] = False
        return np.r_[2,3,((3*np.nonzero(sieve)[0] + 1)|1)]
    @classmethod
    def primes_sieve(cls, n):
        if cls._has_numpy():
            return cls._primes_sieve_np_fast(n)
        else:
            return cls._primes_sieve_pp(n)
    
    @classmethod
    def pfd(cls, primes, n):
        

        factors = []
        cur = n
        for p in primes:
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    factors.append(p)
                    cur = div
                else:
                    break
        assert(cur == 1)
        return factors
    
    @classmethod
    def aliquots(cls, n):
        pf = cls.pfd(n)
        pfc = Counter(pf)
        ppv = [[pow(p, i) for i in range(n+1)] for p,n in pfc.items()]
        if not ppv:
            return (1,)
        else:
            return map(lambda x: reduce(operator.imul, x), product(*ppv))

    @classmethod
    def aliquots_n(cls, n):
        pf = cls.pfd(n)
        pfc = Counter(pf)
        ppv = [[pow(p, i) for i in range(n+1)] for p,n in pfc.items()]
        if not ppv:
            return 1
        else:
            return reduce(operator.imul, [len(x) for x in ppv])

import math
fact = math.factorial
N = int(input())

from collections import Counter
primes = PrimeUtils.primes_sieve(N)

cc = Counter()
for n in range(N):
    cc += Counter(PrimeUtils.pfd(primes, n + 1))

cn = Counter()
for n in cc.values():
    if n >= 2:
        cn[3] += 1
    if n >= 4:
        cn[5] += 1
    if n >= 14:
        cn[15] += 1
    if n >= 24:
        cn[25] += 1
    if n >= 74:
        cn[75] += 1
print(sum([
      cn[75],
      cn[15] * (cn[5] - 1) ,
      cn[25] * (cn[3] - 1) ,
      max(0, (cn[3] - cn[5])) * max(0, cn[5]) * max(0, (cn[5] - 1)) // 2,
      cn[5] * max(0, (cn[5] - 1)) * max(0, (cn[5] - 2)) // 2
      ]))

Solution (Python):
import copy
def prime_decomposition(n, table):
  i = 2
  while i * i <= n:
    c = 0
    while n % i == 0:
      n /= i
      c+=1
    if c!=0:
        if i not in table:
            table[i] = c
        else:
            table[i] += c
    i += 1
  if n > 1:
    if int(n) not in table:
        table[int(n)] = 1
    else:
        table[int(n)] += 1
  return table

table = {}
for i in range(int(input().strip())):
    table = prime_decomposition(i+1, table)

def find_224(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    if ns[depth] == 4:
        ccc = 0
        for i in n_ttt:
            if n_ttt[i] >= 4:
                ccc += 1
        return (ccc * (ccc -1) )// 2

    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            tmp = n_ttt[i]
            del n_ttt[i]
            counter += find_224(ns, n_ttt, depth + 1, counter)
            n_ttt[i] = tmp
    return counter

def find_n(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            if len(ns) == depth + 1:
                counter += 1
            else:
                tmp = n_ttt[i]
                del n_ttt[i]
                counter += find_n(ns, n_ttt, depth + 1, counter)
                n_ttt[i] = tmp
    return counter


res = 0
res += find_224([2, 4], table, 0, 0)

res += find_n([14, 4], table, 0, 0)
res += find_n([24, 2], table, 0, 0)
res += find_n([74], table, 0, 0)
print(res)

Solution (Python):
def dfs(f, r):
    if r==1:
        return 1
    if len(f) == 0:
        return 0


    out = dfs(f[1:], r)
    for i in range(1, min(r, f[0][1])+1):
        if r%(i+1) == 0:
            out += dfs(f[1:], r//(i+1))
    return out

N = int(input())
s = 0

fact = {}
for j in range(2, N+1):
    s = 0
    k = j
    while s==0:
        for i in range(2,k+1):
            if k%i==0:
                k=int(k/i)
                if k==1:
                    s=1
                fact[i] = fact.get(i, 0)+1
                break

fact = list(fact.items())
res = dfs(fact, 75)
print(res)

Solution (Python):
n = int(input())
factor = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
factor_num = [0] * len(factor)
if n <= 9:
	print(0)
else:
	for i in range(2, n+1):
		for j in range(len(factor)):
			cnt = 0
			while i % factor[j] == 0:
				cnt += 1
				i = i // factor[j]
			factor_num[j] += cnt

	

	two_three = 0
	over_four = 0
	over_fourteen = 0
	over_twentyfour = 0
	over_seventyfour = 0

	for i in range(len(factor)):
		if 2 <= factor_num[i] <= 3:
			two_three += 1
		elif factor_num[i] >= 4:
			over_four += 1
			if factor_num[i] >= 14:
				over_fourteen += 1
			if factor_num[i] >= 24:
				over_twentyfour += 1
			if factor_num[i] >= 74:
				over_seventyfour += 1

	

	ans = two_three * (over_four * (over_four - 1) // 2) + over_four * ((over_four - 1) * (over_four - 2) // 2)
	ans += over_fourteen * (over_four - 1) + over_twentyfour * (two_three + over_four - 1)
	ans += over_seventyfour

	print(ans)

Solution (Python):
import math

n=int(input())
a=math.factorial(n)



def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
ps=prime_factors(a)
sy={}
for i in ps:
    if i not in sy:
        sy[i]=1
    else:
        sy[i]+=1


count75=0
count25=0
count15=0
count5=0
count3=0
for k in sy.values():
    
    if k+1>=75:
        count75+=1
    if k+1>=25:
        count25+=1
    if k+1>=15:
        count15+=1
    if k+1>=5:
        count5+=1
    if k+1>=3:
        count3+=1





print(int(count75+count25*(count3-1)+count15*(count5-1)+(count5*(count5-1)*(count3-2))/2))

Solution (Python):
N = int(raw_input())
prime_in_N = {}
for n in range(2, N+1):
  while True:
    bn = n
    for p in (2, 3, 5, 7):
      if n % p == 0:
        n /= p
        if not p in list(prime_in_N.keys()):
          prime_in_N[p] = 0
        prime_in_N[p] += 1
    if bn == n:
      break
  if n > 7:
    if not n in list(prime_in_N.keys()):
      prime_in_N[n] = 0
    prime_in_N[n] += 1
ans = 0
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 74:
	ans += 1
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 2:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 24:
        ans += 1
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 4:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 14:
        ans += 1
tmp_ans = 0
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 2:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 4:
        for c in set(prime_in_N.keys())-set([a])-set([b]):
      		if prime_in_N[c] >= 4:
        		tmp_ans += 1
print ans+tmp_ans/2

Solution (Python):
import math

n = int(input())
pt = [True for i in range(n + 1)]
ps = []
for i in range(2, n + 1):
    if pt[i]:
        ps.append(i)
        m = i * 2
        while m <= n:
            pt[m] = False
            m += i

ans = 0
fa = math.factorial(n)

for p in ps:
    po = p ** 74
    if fa % po == 0:
        ans += 1
    for q in ps:
        if q == p:
            continue
        po = (p ** 2) * (q ** 24)
        if fa % po == 0:
            ans += 1
        po = (p ** 4) * (q ** 14)
        if fa % po == 0:
            ans += 1
        for r in ps:
            if r == p or r <= q:
                continue
            po = (p ** 2) * (q ** 4) * (r ** 4)
            if fa % po == 0:
                ans += 1

print(ans)

Solution (Python):
n = int(input())

pf_list = []
pf_list.append(n//2+ n//4+ n//8+ n//16+ n//32+ n//64)
pf_list.append(n//3+ n//9+ n//27+ n//81)
pf_list.append(n//5+ n//25)
pf_list.append(n//7+ n//49)
pf_list.append(n//11); pf_list.append(n//13); pf_list.append(n//17); pf_list.append(n//19)
pf_list.append(n//23); pf_list.append(n//29); pf_list.append(n//31); pf_list.append(n//37)
pf_list.append(n//41); pf_list.append(n//43); pf_list.append(n//47)


a = [1 if i >= 74 else 0 for i in pf_list]
b = [1 if i >= 24 else 0 for i in pf_list]
c = [1 if i >= 14 else 0 for i in pf_list]
d = [1 if i >= 4 else 0 for i in pf_list]
e = [1 if i >= 2 else 0 for i in pf_list]

ans = 0
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        for k in range(j):
            if i == k:
                continue
            ans += e[i]*d[j]*d[k]
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        ans += e[i]*b[j]
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        ans += d[i]*c[j]
for i in range(15):
    ans += a[i]

print(ans)

Solution (Python):
import collections
import functools
import itertools
import math
import operator


N = int(input())


def get_prime_factorized(N):
    R = []
    b, e = 2, 0
    while b ** 2 <= N:
        while N % b == 0:
            N  = N // b
            e += 1
        if e > 0:
            R.append([b, e])
        b, e = b + 1, 0
    if N > 1:
        R.append([N, 1])
    return R

def n_C_r(n, r):
    return int(math.factorial(n) / math.factorial(r) / math.factorial(n-r))

if N > 9:
    L = [l[1]+1 for l in get_prime_factorized(math.factorial(N))]
    L = [[3, 5, 15, 25, 75] if l >= 75 else [3, 5, 15, 25] if l >= 25 else [3, 5, 15] if l >= 15 else [3, 5] if l >= 5 else [3] if l >= 3 else [1] for l in L]
    L = [l for l in L if l != [1]]
    L = list(itertools.chain.from_iterable(L))
    C = collections.Counter(L)

    R = C[75] + n_C_r(C[5], 2) * n_C_r(C[3]-2, 1) + C[25] * (C[3] - 1) + C[15] * (C[5] - 1)

    print(R)
else:
    print(0)

Solution (Python):
N = int(input())

primes = {}

for i in range(2, N+1):
    tmpN = i
    n = 2
    while tmpN > 1:
        while tmpN%n == 0:
            tmpN //= n
            if n in primes:
                primes[n] += 1
            else:
                primes[n] = 1
        n += 1

kumi5 = 0
kumi3 = 0
kumi75 = 0
kumi25 = 0
kumi15 = 0
for key in primes.keys():
    if primes[key] >= 74:
        kumi75 += 1
    if primes[key] >= 24:
        kumi25 += 1
    if primes[key] >= 14:
        kumi15 += 1
    if primes[key] >= 4:
        kumi5 += 1
    if primes[key] >= 2:
        kumi3 += 1


ans = 0
if kumi5 >= 2 and kumi3 >= 3:
    ans += (kumi5 * (kumi5-1) // 2) * (kumi3-2)

if kumi75 >= 1:
    ans += kumi75

if kumi25 >= 1 and kumi3 >= 2:
    ans += kumi25 * (kumi3-1)

if kumi15 >= 1 and kumi5 >= 2:
    ans += kumi15 * (kumi5-1)

print(ans)

Solution (Python):
def f2(p):
    return 2*p
def f4(p):
    if p<5:
        return 3*p
    else:
        return 4*p
def f14(p):
    if p==2:
        return 16
    elif p==3:
        return 30
    elif p==5:
        return 60
    elif p==7:
        return 91
    else:
        return 101
def f24(p):
    if p==2:
        return 28
    elif p==3:
        return 54
    elif p==5:
        return 100
    else:
        return 101
def f74(p):
    if p==2:
        return 78
    else:
        return 101
    
P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

N = int(input())
c2=0
c4=0
c14=0
c24=0
c74=0

for p in P:
    if f2(p)<=N:
        c2 += 1
    if f4(p)<=N:
        c4 += 1
    if f14(p)<=N:
        c14 += 1
    if f24(p)<=N:
        c24 += 1
    if f74(p)<=N:
        c74 += 1


ans = 0
ans += (c4*(c4-1)//2)*(c2-2)
ans += c14 * (c4 - 1)
ans += c24 * (c2 - 1)
ans += c74

print(ans)

Solution (Python):



res = {}
dp = [[0 for j in range(80)] for i in range(30)]


def pf(n):
    c = 2
    while c * c <= n:
        while not n % c:
            res[c] = res.get(c, 0) + 1
            n //= c
        c += 1

    if n != 1:
        res[n] = res.get(n, 0) + 1


def main():
    n = int(input())

    for i in range(2, n+1):
        pf(i)

    a = [res[k] for k in res]
    for i in range(30):
        dp[i][1] = 1
    for i in range(len(a)):
        for j in range(80):
            dp[i+1][j] = dp[i][j]
            for k in range(1, min(a[i]+1, j+1)):
                if not j % (k+1):
                    dp[i+1][j] += dp[i][j//(k+1)]

    print(dp[len(a)][75])


if __name__ == '__main__':
    main()

Solution (Python):
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
    
a = int(input())
fac = dict()
for i in range(a + 1):
	for k in prime_factors(i):
		if k not in fac:
			fac[k]  = 1
		else:
			fac[k] += 1

for i in list(fac):
	if fac[i] == 1:
		fac.pop(i)

out = 0
for i in fac:
	if fac[i] >= 74:
		out += 1
		
for i in fac:
	if fac[i] >= 24:
		for j in fac:
			if i != j and fac[j] >= 2:
				out += 1
					
for i in fac:
	if fac[i] >= 14:
		for j in fac:
			if i != j and fac[j] >= 4:
				out += 1
		
used = dict()
for i in fac:
	if fac[i] >= 4:
		for j in fac:
			if i != j and tuple(sorted([i,j])) not in used and fac[j] >= 4:
				used[tuple(sorted([i,j]))] = 1
				for k in fac:
					if k != i and k != j and fac[k] >= 2:
						out += 1

print(out)

Solution (Python):
from collections import defaultdict
N = int(input())
primes = defaultdict(int)
for i in range(N):
  n = i + 1
  p = 2
  while n >= p:
    while n % p == 0:
      primes[p] += 1
      n //= p
    p += 1
  if n > 1:
    primes[n] += 1
P = [0, 0, 0, 0, 0]
for p, v in primes.items():
  if v >= 74:
    P[0] += 1
  elif v >= 24:
    P[1] += 1
  elif v >= 14:
    P[2] += 1
  elif v >= 4:
    P[3] += 1
  elif v >= 2:
    P[4] += 1
for i in range(4):
  P[i + 1] += P[i]
cnt = 0
cnt += P[0]
cnt += P[1] * (P[4] - 1)
cnt += P[2] * (P[3] - 1)
cnt += P[3] * (P[3] - 1) // 2 * (P[4] - 2)
print(cnt)

Solution (Python):
from collections import defaultdict
from itertools import combinations

def factorize(n, fct):
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] += e
        b, e = b + 1, 0
    if n > 1:
        fct[n] += 1
    return fct


N = int(input())
d = defaultdict(lambda: 0)
for i in range(N+1):
    d = factorize(i, d)


keys = list(d.keys())

certificates = []

for k in keys:
    if d[k] >= 2:
        certificates.append(k)


res = 0
        
for i,j,k in combinations(certificates, 3):
    if d[j] >= 4 and d[k] >= 4:
        res += 1
    if d[i] >= 4 and d[k] >= 4:
        res += 1
    if d[i] >= 4 and d[j] >= 4:
        res += 1

for i,j in combinations(certificates, 2):
    if d[i] >= 24:
        res += 1
    if d[j] >= 24:
        res += 1
        
for i,j in combinations(certificates, 2):
    if d[i] >= 4 and d[j] >= 14:
        res += 1
    if d[j] >= 4 and d[i] >= 14:
        res += 1
    
for i in certificates:
    if d[i] >= 74:
        res += 1

print(res)

Solution (Python):
import math

def is_prime(n):
    if n==1:
        return False
    for i in range(n-2):
        if n % (i+2) == 0:
            return False
    return True

prime_list = []
for i in range(100):
    if is_prime(i+1):
        prime_list.append(i+1)


factor_list = [0] * len(prime_list)

N = int(input())

for i in range(N):
    for p in prime_list:
        j = i+1
        while j % p == 0:
            factor_list[prime_list.index(p)] += 1
            j = j / p

ans = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 74:
        ans += 1

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 14:
        cnta += 1
    if factor_list[i] >= 4:
        cntb += 1
ans += cnta * (cntb-1)

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 24:
        cnta += 1
    if factor_list[i] >= 2:
        cntb += 1
ans += cnta * (cntb-1)

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 4:
        cnta += 1
    if factor_list[i] >= 2:
        cntb += 1
ans += cnta * (cnta-1) * (cntb-2) /2

print(int(ans))

Solution (Python):

import sys

N = int(input())


ptab = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
atab = [1] * (N + 1) 


memo = [None] * (N + 1)
pidx = 0
cnt = 0
for i in range(2, N + 1):
    tmp = i
    
    for p in ptab:
        
        if tmp in ptab:
            atab[tmp] += 1
            break
        elif tmp < 2: break
        elif tmp % p > 0: continue
        
        for a in range(1, N):
            cnt += 1
            if tmp % (p ** (a + 1)) > 0: break
        
        tmp = tmp // (p ** a)
        atab[p] += a
        


atab_small = []
for maxa in atab:
    if maxa > 1: atab_small.append(maxa)
N = len(atab_small)


def count(pos, val):
    if pos == N or val == 75: return 0
    ret = 0
    for atmp in range(1, atab_small[pos] + 1): 
        if atmp not in [1, 3, 5, 15, 25, 75]: continue
        val_tmp = val * atmp
        if val_tmp < 75: ret += count(pos + 1, val_tmp)
        elif val_tmp == 75: ret += 1
        else: break
    return ret

print(count(0, 1))

Solution (Python):
N = int( input())
W = [0]*101
for i in range(2,N+1):
    j = i
    for k in range(2,100):
        while j%k == 0:
            W[k] += 1
            j //= k
ans = 0
if N >= 78:
    ans += 1
for i in range(2,N+1):
    if W[i] >= 2:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 24:
                ans += 1
for i in range(2,N+1):
    if W[i] >= 4:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 14:
                ans += 1

for i in range(2,N+1):
    if W[i] >= 2:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 4:
                for k in range(j,N+1):
                    if k == i or k == j:
                        continue
                    if W[k] >= 4:
                        ans += 1

print(ans)