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):
import math
import random


class Prime:
    seed_primes = [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]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        
        witnesses = self.get_witnesses(n)
        

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes
prime = Prime()
N = int(input())
def merge_dict_add_values(d1, d2):
    return dict(Counter(d1) + Counter(d2))
from collections import Counter
add_dict = {}
for i in range(N):
    add_dict = merge_dict_add_values(add_dict,prime.find_factors(i+1))
import numpy as np
a= np.array(list(add_dict.values()))
print(int((len(a[a>1])-2)*len(a[a>3])*(len(a[a>3])-1)/2)
      +int(len(a[a>=74]))
      +int(len(a[a>=24]))*(int(len(a[a>=2]))-1)
      +int(len(a[a>=14]))*(int(len(a[a>=4]))-1))

Solution (Python):
PRIME_NUMBER_U48 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]


def main():
    n = int(input())
    prime_counter = {p: 0 for p in PRIME_NUMBER_U48}
    for p in PRIME_NUMBER_U48:
        tmp = n
        while tmp > 0:
            tmp = tmp // p
            prime_counter[p] += tmp

    ans = 0
    for p in prime_counter:
        if prime_counter[p] >= 74:
            ans += 1
        if prime_counter[p] >= 24:
            for i in prime_counter:
                if i != p and prime_counter[i] >= 2:
                    ans += 1
        if prime_counter[p] >= 14:
            for i in prime_counter:
                if i != p and prime_counter[i] >= 4:
                    ans += 1

    two_or_three = [p for p in prime_counter if prime_counter[p] == 2 or prime_counter[p] == 3]
    over_three = [p for p in prime_counter if prime_counter[p] >= 4]
    tot_size = len(two_or_three)
    ot_size = len(over_three)
    if tot_size > 0 and ot_size >= 2:
        ans += tot_size * ot_size * (ot_size - 1) // 2
    if ot_size >= 3:
        ans += ot_size * (ot_size - 1) * (ot_size - 2) // 2

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys 


N = int(input())

def fact(e, n):
  i = 2
  while(n > 1 and i <= n):
    if n % i == 0:
      n //= i
      if i in e:
        e[i] += 1
      else:
        e[i] = 1
    else:
      i += 1

def cnt75(elem_v, elem_75):
  ans = 1
  for i in range(len(elem_75)):
    n = 0
    for j in elem_v:
      if j >= elem_75[i]:
        n += 1
    ans *= (n-i)
  return ans    

def cnt75_2(elem_v):
  ans = 1
  n = 0
  m = 0
  for i in elem_v:
    if i >= 4:
      n += 1
    if i >= 2:
      m += 1
  return n*(n-1)//2 * (m-2)

elem = {}
for n in range(2, N+1):
  fact(elem, n)
elem_v = sorted(elem.values())

ans = cnt75(elem_v,[74])
ans += cnt75(elem_v,[24,2])
ans += cnt75(elem_v,[14,4])
ans += cnt75_2(elem_v)

print(ans)

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

sosuu = []
for i in range(2, N + 1):
    flag = True
    for s in sosuu:
        if i % s == 0:
            flag = False
            break
    if flag:
        sosuu.append(i)

disolvers = [[], []]
for i in range(2, N + 1):
    ret = [0] * len(sosuu)
    t = i
    while t > 1:
        for i, s in enumerate(sosuu):
            if t % s == 0:
                t = t // s
                ret[i] += 1
                break
    disolvers.append(ret)

















d_count = [0] * len(sosuu)
for i in range(2, N + 1):
    di = disolvers[i]
    for i, d in enumerate(di):
        d_count[i] += d

created_numbers = []
def count_numbers(depth, pow_count, used_idx, curr):
    if depth == len(pow_count):
        di = disolvers[N]
        t = 1
        for i in range(len(pow_count) - 1, -1, -1):
            idx = curr[i]
            t = t * (sosuu[idx] ** pow_count[i])
        if t in created_numbers:
            return 0
        created_numbers.append(t)
        return 1
    num = pow_count[depth]
    ret = 0
    for i in range(len(d_count)):
        n = d_count[i]
        if n >= num and i not in used_idx:
            u2 = used_idx + [i]
            ret += count_numbers(depth + 1, pow_count, u2, curr + [i])
    return ret

total = 0
total += count_numbers(0, [4, 4, 2], [], [])
total += count_numbers(0, [24, 2], [], [])
total += count_numbers(0, [14, 4], [], [])
total += count_numbers(0, [74], [], [])

print(total)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(N):
    ps = eratosthenes(100)
    ps.pop(0)
    c = Counter()
    for i in range(2, N+1):
        n = i
        while n not in ps:
            for p in ps:
                if n % p == 0:
                    c[p] += 1
                    n //= p
                    break
        c[n] += 1

    c2 = len(list(filter( lambda x: x>=2, c.values())))
    c4 = len(list(filter( lambda x: x>=4, c.values())))
    c14 = len(list(filter( lambda x: x>=14, c.values())))
    c24 = len(list(filter( lambda x: x>=24, c.values())))
    c74 = len(list(filter( lambda x: x>=74, c.values())))
    ans = 0
    if c2 >= 3 and c4 >= 2:
        ans += (c4*(c4-1)//2) * (c2-2)
    if c4 > 0 and c14 > 0:
        ans += (c4-1) * c14
    if c2 > 0 and c24 > 0:
        ans += (c2-1) * c24
    if c74 > 0:
        ans += c74
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(N):
    ps = eratosthenes(100)
    ps.pop(0)
    c = Counter()
    for i in range(2, N+1):
        n = i
        while n not in ps:
            for p in ps:
                if n % p == 0:
                    c[p] += 1
                    n //= p
                    break
        c[n] += 1

    c2 = len(list(filter( lambda x: x>=2, c.values())))
    c4 = len(list(filter( lambda x: x>=4, c.values())))
    c14 = len(list(filter( lambda x: x>=14, c.values())))
    c24 = len(list(filter( lambda x: x>=24, c.values())))
    c74 = len(list(filter( lambda x: x>=74, c.values())))
    ans = 0
    if c2 >= 3 and c4 >= 2:
        ans += (c4*(c4-1)//2) * (c2-2)
    if c4 > 0 and c14 > 0:
        ans += (c4-1) * c14
    
    if c2 > 0 and c24 > 0:
        ans += (c2-1) * c24
    if c74 > 0:
        ans += c74
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Solution (Python):

N = int(input())

num = [0 for _ in range(N+1)]
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            num[j] += 1
            cur //= j


def Count(m):
    return len(list(filter(lambda x: x >= m - 1, num)))


ans = Count(75) + (Count(3)-1)*Count(25) + Count(15) * (Count(5)-1)\
      + Count(5)*(Count(5)-1)*(Count(3)-2)//2
print(ans)

Solution (Python):

N = int(input())

num = [0 for _ in range(N+1)]
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            num[j] += 1
            cur //= j


def Count(m):
    return len(list(filter(lambda x: x >= m - 1, num)))


ans = Count(75) + (Count(3)-1)*Count(25) + Count(15) * (Count(5)-1)\
      + Count(5)*(Count(5)-1)*(Count(3)-2)//2
print(ans)

Solution (Python):
N, = (int(x) for x in input().split())

n_prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

n_prime_sum = [0]*len(n_prime)
for n in range(1, N+1):
    for i, p in enumerate(n_prime):
        np = 0
        n_c = n
        while(n_c % p == 0):
            n_c = n_c // p
            np += 1
        n_prime_sum[i] += np

p_2 = len([0 for x in n_prime_sum if x >= 2])
p_4 = len([0 for x in n_prime_sum if x >= 4])
p_14 = len([0 for x in n_prime_sum if x >= 14])
p_24 = len([0 for x in n_prime_sum if x >= 24])
p_74 = len([0 for x in n_prime_sum if x >= 74])

n_75 = (p_2-p_4)*p_4*(p_4-1)//2 + p_4*(p_4-1)*(p_4-2)//2 + p_14*(p_4-1) + p_24*(p_2-1) + p_74
print(n_75)

Solution (Python):
def prime_fact(n: int) -> dict:
    ret = {}
    div = 2
    while n >= div:
        if n % div == 0:
            n //= div
            ret[div] = 1
        while n % div == 0:
            n //= div
            ret[div] += 1
        if div == 2:
            div += 1
        else:
            div += 2
    return ret


def fact(n: int) -> int:
    if n < 0:
        return -1
    if n == 0:
        return 1
    return n*fact(n-1)


def q756(N: int) -> int:
    f = fact(N)
    p = prime_fact(f)

    
    c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
    for v in p.values():
        if v >= 74:
            c74 += 1
        if v >= 24:
            c24 += 1
        if v >= 14:
            c14 += 1
        if v >= 4:
            c4 += 1
        if v >= 2:
            c2 += 1

    ret = c74
    if c2 > 1:
        ret += c24 * (c2-1)
    if c4 > 1:
        ret += c14 * (c4-1)
    if c2 > 2 and c4 > 1:
        ret += ((c4 * (c4-1)) // 2) * (c2-2)

    return ret


if __name__ == "__main__":
    N = int(input())
    ans = q756(N)
    print(ans)

Solution (Python):
n = int(input())
prits = [0 for i in range(n+1)]

for i in range(1,n+1):
    k = 2
    while k*k<=i:
        while i%k == 0:
            i = i//k
            prits[k] += 1
        k += 1
    if i>1 :
        prits[i] += 1


a,b,c,d,e = [],[],[],[],[]

for i in range(len(prits)):
    num = prits[i]
    if num >=2:
        e.append(i)
    if num >=4:
        d.append(i)
    if num >=14:
        c.append(i)
    if num >=24:
        b.append(i)
    if num >=74:
        a.append(i)



ans = 0
ans += len(a)
ans += len(c)*(len(d)-1)
ans += len(b)*(len(e)-1)
ans += len(d)*(len(d)-1)*(len(e)-2)//2

print(ans)

Solution (Python):
from collections import defaultdict
import itertools
N = int(input())
dic = defaultdict(int)
for i in range(2, N+1):
    for j in range(2, i + 1):
        while i % j == 0:
            i /= j
            dic[j] += 1
lst_2 = [k for k, v in dic.items() if v >= 2]
lst_4 = [k for k, v in dic.items() if v >= 4]
lst_14 = [k for k, v in dic.items() if v >= 14]
lst_24 = [k for k, v in dic.items() if v >= 24]
lst_74 = [k for k, v in dic.items() if v >= 74]
z = list(itertools.combinations(lst_4, 2))
p_2_q_4_r_4 = len([x for x in list(itertools.product(lst_2, z)) if x[0] != x[1][0] and x[0] != x[1][1]])
p_14_q_2 = len(lst_14) * len(lst_4) - len([x for x in lst_14 if x in lst_4])
p_2_q_24 = len(lst_2) * len(lst_24) - len([x for x in lst_2 if x in lst_24])
p_74 = len([k for k, v in dic.items() if v >= 74])
print(p_2_q_4_r_4 + p_14_q_2 + p_2_q_24 + p_74)

Solution (Python):
N = int(input())
def sieve(n):
    num = [True]*n
    num[0]=num[1]= False
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = False
    return ([i for i in range(2,n) if num[i]])
s = sieve(100)
fact = [[i,0] for i in s]
for i in range(2,N+1):
    j = i
    for m in range(len(s)):
        if j == 1:
            break
        while j % s[m] == 0:
            j = j // s[m]
            fact[m][1] += 1

factor_num = [i[1] for i in fact]
def multi_index(l, x): 
    return [i for i, _x in enumerate(l) if _x >= x]
n75 = 0
if sum([1 for i in factor_num if i >= 4]) >= 2:
    over4 = multi_index(factor_num,4)
    over2 = multi_index(factor_num,2)
    for i in range(len(over4)):
        for j in range(i,len(over4)):
            for k in range(len(over2)):
                if i!=j and over4[i]!=over2[k] and over4[j]!=over2[k]:
                    n75 += 1
    try:
        over24 = multi_index(factor_num,24)
        for i in over24:
            for j in over2:
                if i!= j:
                    n75 += 1
    except:
        pass

    try:
        over14 = multi_index(factor_num,14)
        for i in over14:
            for j in over4:
                if i != j:
                    n75 += 1
    except:
        pass

    try:
        over74 = multi_index(factor_num,74)
        n75 += len(over74)
    except:
        pass
print(n75)

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
INF = 10**18

N=ri()
pri = [0]*101

for i in range(1,N+1):
    b = 2
    while b*b <= i:
        while i%b == 0:
            i //= b
            pri[b] += 1
        b += 1
    if i > 1:
        pri[i] += 1

exp = []
for i in range(101):
    if pri[i] > 0:
        exp += [pri[i] + 1]

exp.sort()
exp_len = len(exp)
import bisect
cnt_75 = exp_len - bisect.bisect_left(exp,75)
cnt_25 = exp_len - bisect.bisect_left(exp,25)
cnt_15 = exp_len - bisect.bisect_left(exp,15)
cnt_5 = exp_len - bisect.bisect_left(exp,5)
cnt_3 = exp_len - bisect.bisect_left(exp,3)
ans = 0

ans += cnt_75
ans += cnt_25*cnt_3 - cnt_25
ans += cnt_15*cnt_5 - cnt_15
ans += cnt_5*(cnt_5-1)/2*cnt_3 - cnt_5*(cnt_5-1)/2*2
ans = int(ans)

print(ans)

Solution (Python):
from collections import Counter


def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

yakusu = []
n = int(input())
for i in range(1, n+1):
    yakusu += prime_factor(i)
c = Counter(yakusu)
d = {}
for ik, iv in c.items():
    for jk, jv in c.items():
        for kk, kv in c.items():
            if len(set([ik, jk, kk])) != 3:
                continue
            if iv >= 74:
                d[ik**74] = 0
            if iv >= 24 and jv >= 2:
                d[(ik**24)*(jk**2)] = 0
            if iv >= 14 and jv >= 4:
                d[(ik**14)*(jk**4)] = 0
            if iv >= 4 and jv >= 4 and kv >= 2:
                d[(ik**4)*(jk**4)*(kk**2)] = 0
print(len(d.values()))

Solution (Python):
N=int(input())
e=[0]*(N+1)
for i in range(2,N+1):
    cur=i
    for j in range(2,i+1):
        while cur%j==0:
            e[j]+=1
            cur//=j
def num(m):return len(list(filter(lambda x:x>=m-1,e)))
print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)

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

if n < 10:
    print(0)
    exit()

e = [0 for _ in range(n + 1)]

for i in range(2, n + 1):
    temp = i
    for j in range(2, i + 1):
        while temp % j == 0:
            e[j] += 1
            temp //= j

a = [0 for _ in range(75)]
for i in range(n + 1):
    for j in range(min(75, e[i] + 1)):
        a[j] += 1

ans = a[74] + a[24] * (a[2] - 1) + a[14] * (a[4] - 1) + a[4] * (a[4] - 1) * (a[2] - 2) // 2
print(ans)

Solution (Python):



from collections import Counter
import sys
input = sys.stdin.readline

def divisors(n):
    ret = {}
    tmp = n
    for p in [2, 3, 5, 7]:
        d = 0
        while tmp % p == 0:
            tmp /= p
            d += 1
        if d > 0:
            ret[p] = d
    if tmp > 1:
        ret[int(tmp)] = 1
    return ret


def main():
    patterns = [(5, 5, 3), (15, 5), (25, 3), (75)]
    N = int(input())
    divs = Counter()
    for n in range(1, N+1):
        divs.update(divisors(n))
    l = [0] * 5
    for i, p75 in enumerate([75, 25, 15, 5, 3]):
        for p, cnt in divs.most_common():
            if cnt >= p75-1:
                l[i] += 1
    ret = 0
    ret += l[0] 
    ret += l[1] * (l[4]-1) 
    ret += l[2] * (l[3]-1) 
    ret += (l[3] * (l[3]-1) / 2) * (l[4]-2) 
    print(int(ret))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
from collections import Counter
c = Counter()
for i in range(1,n+1):
    for j in range(2, i+1):
        while i % j == 0:
            c[j] += 1
            i //= j

def num(a):
    ret = 0
    for key, value in c.items():
        if value >= a:
            ret += 1
    return ret

ans = num(74) + num(24) * (num(2)-1) + num(14)*(num(4)-1) + num(4)*(num(4)-1)//2*(num(2) - 2)
print(ans)

Solution (Python):
from collections import Counter
def facrorize(n):
    c = Counter()
    t = 2
    while t**2 <= n:
        if n%t:
            t += 1
            continue
        while not n%t:
            c[t] += 1
            n //= t
    if n > 1:
        c[n] += 1
    return c

def comb(n, r):
    r = min(r, n-r)
    if n < 0 or r < 0:return 0
    ret = 1
    for i in range(r):
        ret = ret*(n-i)//(i+1)
    return ret

n = int(input())
d = Counter()
for i in range(1, n+1):
    c = facrorize(i)
    for key, value in c.items():
        d[key] += value

e = {2:[],4:[],14:[],24:[],74:[]}
for key, value in d.items():
    for cnt in e:
        if value >= cnt:
            e[cnt].append(key)

ans = 0

for two in e[2]:
    if two not in e[4]:
        ans += comb(len(e[4]), 2)
    else:
        ans += comb(len(e[4])-1, 2)
    
    if two not in e[24]:
        ans += len(e[24])
    else:
        ans += comb(len(e[24])-1,1)


for four in e[4]:
    if four not in e[14]:
        ans += len(e[14])
    else:
        ans += comb(len(e[14]) - 1, 1)

ans += len(e[74])
print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())
if n in [1, 2]:
    print(0)
    exit()

count_primes = defaultdict(int, {})
for m in range(2, n+1):
    p = 2
    while p**2 <= m:
        while m%p == 0:
            m //= p
            count_primes[p] += 1
        p += 1
    if m > 1:
        count_primes[m] += 1


count_div = [0]*100
for _, c in count_primes.items():
    for i in range(c+1):
        count_div[i] += 1


ans = count_div[74] + count_div[24]*(count_div[2]-1) \
    + count_div[14]*(count_div[4]-1) + count_div[4]*(count_div[4]-1)//2*(count_div[2]-2)
print(ans)

Solution (Python):


from math import factorial

N = int(input())
answer = 0

primeN = (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)
amount = []

for i in primeN:
    amount.append(1)

for n in range(N):
    n = n + 1
    for m in range(len(primeN)):
        m = m + 1
        while n >= primeN[-m]:
            if n % primeN[-m] == 0:
                amount[-m] += 1
                n = n // primeN[-m]
            else: break

for i in amount:
    if i >= 75:
        answer += 1

i1, i2 = 0, 0
for i in amount:
    if i >= 15:
        i1 += 1
    elif i >= 5:
        i2 += 1
if i1 >= 1 and i1+i2 >= 2:
    answer += i1 * (i1+i2-1)

i3,i4 = 0, 0
for i in amount:
    if i >= 25:
        i3 += 1
    if i >= 3:
        i4 += 1
if i3 >= 1 and i4 >= 2:
    answer += i3 * (i4-1)

i5, i6 = 0, 0
for i in amount:
    if i >= 5:
        i5 += 1
    if i >= 3:
        i6 += 1
if i5 >= 2 and i6 >= 3:
    answer += (factorial(i5) // 2 // factorial(i5-2)) * (i6-2)

print(answer)

Solution (Python):
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
s=[0 for i in range(15)]
N=int(input())
for i in range(15):
  j=1
  while N//(prime[i]**j)>0:
    s[i]+=N//(prime[i]**j)
    j+=1
o3,o5,o15,o25,o75=0,0,0,0,0
for item in s:
  if item>=2:
    o3+=1
    if item>=4:
      o5+=1
      if item>=14:
        o15+=1
        if item>=24:
          o25+=1
          if item>=74:
            o75+=1
ans=[0,0,0,0]
if o75>0:
  ans[0]+=1
if o25>0:
  ans[1]+=o25*(o3-1)
if o15>0:
  ans[2]+=o15*(o5-1)
if o5>1 and o3>2:
  ans[3]+=o5*(o5-1)//2*(o3-2)
print(sum(ans))

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

A=[0 for i in range(n+1)] 

for i in range(2,n+1) :
    j=2
    while i!=1 :
        
        if i%j==0 :
            i=i//j
            A[j]+=1
        else :
            j+=1



B=[]
for i in [2,4,14,24,74] :
    co=0
    for j in A :
        if j>=i :
            co+=1
    B.append(co)



print((B[0]-2)*B[1]*(B[1]-1)//2 + (B[1]-1)*B[2] + (B[0]-1)*B[3] + B[4])

Solution (Python):
from collections import Counter
n = int(input())
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
for j in range(2,n+1):
  prime_decomposition(j, table)
c = Counter(table).values()
cc = Counter(c)
count_2 = cc[2] + cc[3]
count_4 = 0
for i in range(4,14):
  count_4+=cc[i]
count_14 = 0
for i in range(14,24):
  count_14+=cc[i]
count_24 = 0
for i in range(24,74):
  count_24+=cc[i]
count_74 = 0
for i in range(74,101):
  count_74+=cc[i]
count_24 += count_74
count_14 += count_24
count_4 += count_14
count_2 += count_4
print(count_74+count_24*max([0,count_2-1])+count_14*max(count_4-1,0)+max([count_2-2,0])*max([count_4-1,0])*count_4//2)

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

import math
def is_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False

    
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step

    return True
  

def make_prime_list(num):
    if num < 2:
        return []

    prime_list = []
    for prime in range(2, num + 1):
        if is_prime(prime):
            prime_list.append(prime)
    return prime_list
  
prime_list = make_prime_list(n)
pcount={}
for p in prime_list:
    pcount[p]=0
for nn in range(2,n+1):
    for p in prime_list:
        n=nn
        if n<p:
            break
        while n%p==0:
            n//=p
            pcount[p]+=1

mcount = {}
for m in [3,5,15,25,75]:
    mcount[m]=0
for i in pcount.values():
    for j in mcount:
        if i >= j - 1:
            mcount[j] += 1
            
print(mcount[75] + mcount[5]*(mcount[5]-1)//2*(mcount[3]-2) + (mcount[3]-1)*mcount[25] + mcount[15] * (mcount[5] - 1))

Solution (Python):
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]
c = [0 for i in range(0, len(p))]

for i in range(0, len(p)):
    m = 1
    pi = p[i]
    while pi <= n:
        c[i] += n // pi
        m += 1
        pi = p[i]**m
        
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0

for i in range(0, len(p)):
    if c[i] >= 2:
        c2 += 1
    if c[i] >= 4:
        c4 += 1
    if c[i] >= 14:
        c14 += 1
    if c[i] >= 24:
        c24 += 1
    if c[i] >= 74:
        c74 += 1

print(c74 + (c4 - c14) * c14 + c14 * (c14 - 1) + (c2 - c24) * c24 + c24 * (c24 - 1) + (c2 - c4) * c4 * (c4 - 1) // 2 + c4 * (c4 - 1) * (c4 - 2) // 2)

Solution (Python):
import math
import collections
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
def count_counter(c,n):
    res = 0
    for i in c.values():
        if i >= n:
            res += 1
    return res
    
n = int(input())
factors, ans = [], 0
for i in range(2,n+1):
    factors = factors + prime_factor(i)
c = collections.Counter(sorted(factors))
ans += count_counter(c,74)
ans += (count_counter(c,24)*(count_counter(c,2)-1))
ans += (count_counter(c,14)*(count_counter(c,4)-1))
ans += ((count_counter(c,4)*(count_counter(c,4)-1)*(count_counter(c,2)-2))//2)
print(ans)

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

def IsPrime(A):
    prime=[2]
    for a in range(3,A+1):
        for p in prime:
            if a%p==0:
                break
        else:
            prime.append(a)
    return prime


prime=IsPrime(N)

pcount={}
for p in prime:
    pcount[p]=0
for nn in range(2,N+1):
    for p in prime:
        n=nn
        if n<p:
            break
        while n%p==0:
            n//=p
            pcount[p]+=1

mcount={}
for i in [75,25,15,5,3]:
    mcount[i]=0
for p in prime:
    for i in [75,25,15,5,3]:
        if pcount[p]>=i-1:
            mcount[i]+=1

print(mcount[75]+\
        mcount[25]*(mcount[3]-1)+\
        mcount[15]*(mcount[5]-1)+\
        mcount[5]*(mcount[5]-1)//2*(mcount[3]-2))

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


def factorization( n, e ):
    for i in range( 2, N+1 ):
        for j in range( 2, i+1 ):
            while i % j == 0:
                e[j] += 1
                i /= j


def num( m ):
    return len( list(filter(lambda x: x>= m-1, e)) )


e = [0]*(N+1)
factorization( N, e )
ans = num(75) + num(25)*(num(3)-1) + num(15)*(num(5)-1) \
      + num(5)*(num(5)-1)*(num(3)-2)//2
print( ans )

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


def factorization( n, e ):
    for i in range( 2, N+1 ):
        for j in range( 2, i+1 ):
            while i % j == 0:
                e[j] += 1
                i /= j


def num( m ):
    return len( list(filter(lambda x: x>= m-1, e)) )


e = [0]*(N+1)
factorization( N, e )
ans = num(75) + num(25)*(num(3)-1) + num(15)*(num(5)-1) \
      + num(5)*(num(5)-1)*(num(3)-2)//2
print( ans )

Solution (Python):
n=int(input())
C=[0]*(n+1)
for i in range(2,n+1):
    tmp=i
    for j in range(2,i+1):
        while tmp%j==0:
            C[j]+=1
            tmp//=j
def num(n):
    return len(list(filter(lambda x:x>=n-1,C)))
print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)