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 sys
input = sys.stdin.readline

n = int(input())

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

from collections import defaultdict

d = defaultdict(int)

for i in range(2, n + 1):
    arr = factorization(i)
    for j in arr:
        d[j[0]] += j[1]
v = d.values()

from collections import Counter

c = Counter(v)
li = [0]*5

for i in c.keys():
    if i >= 2:
        li[0] += c[i] 
    if i >= 4:
        li[1] += c[i] 
    if i >= 14:
        li[2] += c[i] 
    if i >= 24:
        li[3] += c[i] 
    if i >= 74:
        li[4] += c[i] 

ans = 0
ans += li[1] * (li[1] - 1) // 2 * (li[0] - 2)
ans += li[2] * (li[1] - 1)
ans += li[3] * (li[0] - 1)
ans += li[4]

print(ans)

Solution (Python):
def c(n, P):
    return sum([1 for p in P if p + 1 >= n])


N = int(input())
pN = {}
for i in range(N + 1):
    for j in range(2, i + 1):
        while i % j == 0:
            i //= j
            pN[j] = pN.get(j, 0) + 1
V = pN.values()
ans = c(75, V)
ans += c(25, V) * (c(3, V) - 1)
ans += c(15, V) * (c(5, V) - 1)
ans += c(5, V) * (c(5, V) - 1) * (c(3, V) - 2) // 2
print(ans)

Solution (Python):
from collections import Counter
import itertools
import math
def prime(n):
    ma=int(math.sqrt(n))+1
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=ma:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

n=int(input())
if(n<10):
    print(0)
    exit()
primes=prime(n+1)
factor=[]
for i in range(2,n+1):
    tmp=i
    for k in primes:
        while(tmp%k==0):
            tmp//=k
            factor.append(k)
values,counts=zip(*Counter(factor).most_common())
counts=list(counts)
ans=0
for i in counts:
    if(i>=74):
        ans+=1
for k in itertools.combinations(counts,2):
    if(k[0]>=2 and k[1]>=24):
        ans+=1
    if(k[0]>=4 and k[1]>=14):
        ans+=1
    if(k[0]>=24 and k[1]>=2):
        ans+=1
    if(k[0]>=14 and k[1]>=4):
        ans+=1
for k in itertools.combinations(counts,3):
    if(k[0]>=2 and k[1]>=4 and k[2]>=4):
        ans+=1
    if(k[1]>=2 and k[2]>=4 and k[0]>=4):
        ans+=1
    if(k[2]>=2 and k[1]>=4 and k[0]>=4):
        ans+=1
print(ans)

Solution (Python):

n = int(input())

div_cnt = [0] * n

def search_div(data, n):
    while n != 1:
        for i in range(2, n + 1):
            if n % i == 0:
                data[i - 1] += 1
                n = int(n / i)
                break
        

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

def count_num(data, n):
    cnt = 0
    for i in range(len(data)):
        if data[i] >= n - 1:
            cnt += 1
    
    return cnt
print(int(count_num(div_cnt, 75) + count_num(div_cnt, 25) * (count_num(div_cnt, 3) - 1) + count_num(div_cnt, 15) * (count_num(div_cnt, 5) - 1) + count_num(div_cnt, 5) * (count_num(div_cnt, 5) - 1) / 2 * (count_num(div_cnt, 3) - 2)))

Solution (Python):

n = int(input())

div_cnt = [0] * n

def search_div(data, n):
    while n != 1:
        for i in range(2, n + 1):
            if n % i == 0:
                data[i - 1] += 1
                n = int(n / i)
                break
        

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

cnt_2 = 0
cnt_4 = 0
cnt_14 = 0
cnt_24 = 0
cnt_74 = 0
if max(div_cnt) < 4:
    print(0)
    exit()

for i in range(n):
    if div_cnt[i] >= 74:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
        cnt_24 += 1
        cnt_74 += 1
    elif div_cnt[i] >= 24:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
        cnt_24 += 1
    elif div_cnt[i] >= 14:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
    elif div_cnt[i] >= 4:
        cnt_2 += 1
        cnt_4 += 1
    elif div_cnt[i] >= 2:
        cnt_2 += 1
    
ans = cnt_74 + cnt_24 * (cnt_2 - 1) + cnt_14 * (cnt_4 - 1) + (cnt_4 * (cnt_4 - 1)) / 2 * (cnt_2 - 2)
print(int(ans))

Solution (Python):

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

e = [0] * (N + 1)

for i in range(2, N + 1):
    cur = i
    for j in range(2, N + 1):
        while cur % j == 0:
            
            e[j] += 1
            cur //= j
def num(m):
    return len(list(filter (lambda x: x >= m - 1, 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):
from collections import Counter

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


n = int(input())

p_list = []
for i in range(1,n+1):
    p_list = p_list + fctr1(i)

pc = Counter(p_list).most_common()



c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0

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

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

print(ans)

Solution (Python):

N = int(input())


def p_deg_le(pfac, n):
    ret = 0
    for p_deg in pfac:
        if p_deg[1] >= n: ret += 1
        else: break
    return ret



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]


pfac = {} 
for i in range(1, N + 1):
    for p in P:
        while i % p == 0:
            if p in pfac:   pfac[p] += 1
            else:           pfac[p] = 1
            i //= p


pfac = sorted(pfac.items(), reverse = True, key = lambda x : x[1])

fact = 1
for p_deg in pfac:
    fact *= p_deg[0] ** p_deg[1]





p_deg = {}
for deg in (2, 4, 14, 24, 74):
    p_deg[deg] = p_deg_le(pfac, deg)


ans = (p_deg[4] * (p_deg[4] - 1) // 2) * (p_deg[2] - 2)

ans += p_deg[14] * (p_deg[4] - 1)

ans += p_deg[24] * (p_deg[2] - 1)

ans += p_deg[74]

print(ans)

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

N=[0]*(n+1)

def f(n):
    M=[]
    while n%2==0:
        n//=2
        M.append(2)
    i=3
    while n>=i:
        while n%i==0:
            n//=i
            M.append(i)
        i+=2
    return M

for i in range(2,n+1):
    for j in f(i):
        N[j]+=1

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

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

N=[0]*(n+1)

def f(n):
    M=[]
    while n%2==0:
        n//=2
        M.append(2)
    i=3
    while n>=i:
        while n%i==0:
            n//=i
            M.append(i)
        i+=2
    return M

for i in range(2,n+1):
    for j in f(i):
        N[j]+=1

ANS=[0]*5

for i in range(1,n+1):
    if N[i]>=74:
        ANS[0]+=1
    elif N[i]>=24:
        ANS[1]+=1
    elif N[i]>=14:
        ANS[2]+=1
    elif N[i]>=4:
        ANS[3]+=1
    elif N[i]>=2:
        ANS[4]+=1

ANS[1]+=ANS[0]
ANS[2]+=ANS[1]
ANS[3]+=ANS[2]
ANS[4]+=ANS[3]

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from collections import defaultdict

N = int(input())

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


d = defaultdict(list)
d[2]=7
d[3]=4
d[5]=1
d[7]=1


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

for i in range(10,N+1):
    prime_factor(i)

cand2 = 0
cand4 = 0
cand14 = 0
cand24 = 0
cand74 = 0

for key,val in d.items():
    if val >= 2:
        cand2 += 1
        if val >=4:
            cand4 += 1
            if val >=14:
                cand14 += 1
                if val >=24:
                    cand24 += 1
                    if val >=74:
                        cand74 += 1


ans = 0
ans += cand4  * (cand4-1)//2 * (cand2-2)
ans += cand24 * (cand2-1)
ans += cand14 * (cand4-1)
ans += cand74

print(ans)

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

from math import factorial
def comb(n, r):
    if n < r:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

d = {}

for i in range(1, n+1):
    for m, cnt in factorization(i):
        if m == 1:
            continue
        if m in d:
            d[m] += cnt
        else:
            d[m] = cnt

cnt = [0 for i in range(100)]

for k in d:
    cnt[d[k]] += 1

print(
    sum(cnt[74:]) + 
    sum(cnt[4:14]) * sum(cnt[14:]) + sum(cnt[14:]) * (sum(cnt[14:])-1) + 
    sum(cnt[2:24]) * sum(cnt[24:]) + sum(cnt[24:]) * (sum(cnt[24:])-1) + 
    sum(cnt[2:4]) * comb(sum(cnt[4:]), 2) + sum(cnt[4:]) * comb(sum(cnt[4:])-1, 2) 
)

Solution (Python):

import sys

N = int(input().strip())



class factorization():
    def get_divisor(self, n :int) -> dict:
        divisor_dic={}
        
        tmp_num = n
        for i in range(2,n):
            while tmp_num % i == 0:
                divisor_dic.setdefault(i,0)
                divisor_dic[i] += 1
                
                tmp_num //= i
        
        return divisor_dic


divisor_dic={}  
for num in range(2,N+1):
    
    fa = factorization()
    ret = fa.get_divisor(num)

    for key,v in ret.items():
        divisor_dic.setdefault(key,0)
        divisor_dic[key] += v
    
    divisor_dic.setdefault(num,0)
    divisor_dic[num] += 1


cnt_divisor_dic={ i:0 for i in [74,24,14,4,2]}

for key,v in divisor_dic.items():
    for j in [74,24,14,4,2]:
        if v >= j:
            cnt_divisor_dic[j] += 1







sum = cnt_divisor_dic[74] + \
      cnt_divisor_dic[24] * (cnt_divisor_dic[2] - 1) + \
      cnt_divisor_dic[14] * (cnt_divisor_dic[4] - 1) + \
      cnt_divisor_dic[4] * (cnt_divisor_dic[4] - 1) // (2*1) * (cnt_divisor_dic[2] - 2)

print(sum)

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

primes = primes(100)

N = int(input())


e = [0] * (N+1)
for i in range(2,N+1):
    cur = i
    for p in primes:
        while cur % p == 0:
            e[p] += 1
            cur //= p


cnt = lambda M: len(tuple(filter(lambda x: x >= M - 1, e)))

ans = cnt(75) 
ans += cnt(25) * (cnt(3) - 1) 
ans += cnt(15) * (cnt(5) - 1) 

ans += cnt(5) * (cnt(5) - 1) * (cnt(3) - 2) // 2 

print(ans)

Solution (Python):
def the_sieve_of_eratosthenes(i):
    s = [j for j in range(2, i + 1)]
    j = 0
    while True:
        if j >= i - 3:
            for k in range(len(s) - 1, 0, -1):
                if s[k] == 0:
                    del s[k]
            return s
        if s[j] != 0:
            for k in range(2 * s[j] - 2, i - 1, s[j]):
                s[k] = 0
        j += 1

n = int(input())
p = the_sieve_of_eratosthenes(n)
c = [1] * len(p)
for i in range(2, n + 1):
    if not i in p:
        j = 0
        while True:
            if i == 1 or j == len(p):
                break
            if i % p[j] == 0:
                i /= p[j]
                c[j] += 1
            else:
                j += 1
a1, a2, a3, a4, a5 = 0, 0, 0, 0, 0
ans = 0
for i in c:
    if i >= 2:
        a1 += 1
    if i >= 4:
        a2 += 1
    if i >= 14:
        a3 += 1
    if i >= 24:
        a4 += 1
    if i >= 74:
        a5 += 1
ans = ((a1 - 2) * a2 * (a2 - 1) // 2) + (a2 - 1) * a3 + (a1 - 1) * a4 + a5
print(ans)

Solution (Python):
x=[]

for j in range(100):
    m=j+1
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    x.append(pf)

N=int(input())
if N==1:
    print(0)
    exit()

from collections import defaultdict
d=defaultdict(int)
for i in range(1,N):
    for k in x[i].keys():
        d[k]+=x[i][k]


over2=0
over4=0
over14=0
over24=0
over74=0
for k in d.keys():
    if d[k]>=2:
        over2+=1
    if d[k]>=4:
        over4+=1
    if d[k]>=14:
        over14+=1
    if d[k]>=24:
        over24+=1
    if d[k]>=74:
        over74+=1

ans=0

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

ans+=over14*(over4-1)

ans+=over24*(over2-1)

ans+=over74
print(ans)

Solution (Python):
from collections import defaultdict

def factorization(n):
    if n == 1: return []
    res = []
    x = n
    y = 2
    while y * y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

N = int(input())

D = defaultdict(int)

for i in range(1, N + 1):
    F = factorization(i)
    for f in F:
        D[f] += 1

cnt_75 = 0
cnt_25 = 0
cnt_15 = 0
cnt_5 = 0
cnt_3 = 0

for v in D.values():
    if v + 1 >= 75:
        cnt_75 += 1
    if v + 1 >= 25:
        cnt_25 += 1
    if v + 1 >= 15:
        cnt_15 += 1
    if v + 1 >= 5:
        cnt_5 += 1
    if v + 1 >= 3:
        cnt_3 += 1

ans = 0

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

print(ans)

Solution (Python):
def factorization(n):
    d = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            d[i] = cnt
    if temp!=1:
        d[temp] = 1
    if len(d) == 0:
        d[n] = 1
    return d

N = int(input())
fac_dict = {}
for n in range(1, N+1):
  d = factorization(n)
  for p in d:
    if p in fac_dict:
      fac_dict[p] += d[p]
    else:
      fac_dict[p] = d[p]


num_prime = [0, 0, 0, 0, 0]
for p in fac_dict:
  num = fac_dict[p]
  if num >= 2:
    num_prime[4] += 1
    if num >= 4:
      num_prime[3] += 1
      if num >= 14:
        num_prime[2] += 1
        if num >= 24:
          num_prime[1] += 1
          if num >= 74:
            num_prime[0] += 1

ans = 0
ans += num_prime[0] 
ans += num_prime[1] * (num_prime[4]-1) 
ans += num_prime[2] * (num_prime[3]-1) 
ans += (num_prime[3]*(num_prime[3]-1)//2) * (num_prime[4]-2) 
print(ans)

Solution (Python):






n = int(input())


def prime_factorization(n):
    Primes = []
    while n % 2 == 0:
        Primes.append(2)
        n = int(n/2)
    f = 3
    while f*f <= n:
        if n % f == 0:
            Primes.append(f)
            n = int(n/f)
        else:
            f += 2
    if n != 1:
        Primes.append(n)
    return Primes

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

for i in range(2,n+1):
    Primes = prime_factorization(i)
    for prime in Primes:
        Primes_count[prime] += 1


def count(n, Primes_count):
    return len(list(filter(lambda x:x>=n-1, Primes_count)))

ans = 0

ans += count(75, Primes_count)


ans += (count(3, Primes_count)-1) * count(25, Primes_count)


ans += (count(5, Primes_count)-1) * count(15, Primes_count)


ans += (count(5, Primes_count)) * (count(5, Primes_count) -1) * (count(3, Primes_count)-2) // 2

print(ans)

Solution (Python):
N = int(input())
c = [0 for i in range(101)]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

for i in range(2,N+1):
    factors = prime_factorize(i)
    for factor in factors:
        c[factor] += 1
c = [e+1 for e in c]

ans = 0

more75 = len(list(filter(lambda x:x>=75,c)))
more25 = len(list(filter(lambda x:x>=25,c)))
more15 = len(list(filter(lambda x:x>=15,c)))
more5 = len(list(filter(lambda x:x>=5,c)))
more3 = len(list(filter(lambda x:x>=3,c)))

ans += more75
if more25:
    ans += more25*(more3-1)
if more15:
    ans += more15*(more5-1)
if more5 >= 2 and more3 >= 3:
    ans += (more3-2)*(more5*(more5-1))//2
print(ans)

Solution (Python):
def sieve(n):
    prime=[]
    limit=n**0.5
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

def main():
    n=int(input())
    primes=sieve(n+1)
    l=len(primes)

    factor=[]
    for i in range(l):
        p = primes[i]
        cnt = 0
        fac = p
        while fac <= n:
            cnt += n//fac
            fac *= p
        factor.append(cnt)
    
    l2=len(factor)
    idx=[0,0,0,0,0]
    fac=[2,4,14,24,74]
    j,i=4,0
    while i<l2:
        if  factor[i] < fac[j]:
            idx[j] = i
            j-=1
            if j==-1:
                break
        else:
            i+=1

    ans=idx[4]+idx[3]*max(0,idx[0]-1)+idx[2]*max(0,idx[1]-1)+idx[1]*max(0,idx[1]-1)*max(0,idx[0]-2)//2
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
n = int(input())
D = [0]*(n+1)

def check_div_n(div_list, n):
  return len([d for d in div_list if d>=n and d!=0])

for i in range(2, n+1):
  check_n = i
  for j in range(2, n+1):
    while check_n%j==0:
      D[j] += 1
      check_n = check_n//j
      
ans = check_div_n(D, 74) + \
      (check_div_n(D, 4)-1)*check_div_n(D, 14) + \
      (check_div_n(D, 2)-1)*check_div_n(D, 24) + \
      check_div_n(D, 4)*(check_div_n(D, 4)-1)//2 * \
      (check_div_n(D, 2)-2)
  
print(ans)

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

def chk_prime(n):
  for i in range(2,int(math.sqrt(n))+1):
    if n%i==0:
      return False
  return True
primes=[]
for i in range(2,n+1):
  if chk_prime(i):
    primes.append(i)
cc=[0]*len(primes)
for i in range(2,n+1):
  num=i
  for j in range(len(primes)):
    cnt=0
    while num%primes[j]==0:
      num//=primes[j]
      cnt+=1
    cc[j]+=cnt
ans=0

for i in cc:
  if i>=74:
    ans+=1

cnt_24=0
cnt_2=0
for i in cc:
  if i>=24:
    cnt_24+=1
  if i>=2:
    cnt_2+=1
ans+=cnt_24*(cnt_2-1)

cnt_14=0
cnt_4=0
for i in cc:
  if i>=14:
    cnt_14+=1
  if i>=4:
    cnt_4+=1
ans+=cnt_14*(cnt_4-1)

cnt_4=0
for i in cc:
  if i>=4:
    cnt_4+=1
ans+=((cnt_4*(cnt_4-1))//2)*(cnt_2-2)
print(ans)

Solution (Python):
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    count = 0
    for i in range(2, n+1):
        if prime[i]:
            count += 1
            for j in range(2*i, n+1, i):
                prime[j] = False
    return prime


def count(p):
    cnt = 0
    n = N
    while n > 0:
        n //= p
        cnt += n
    return cnt


N = int(input())
prime = sieve(N)
ans = 0


for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 74:
        break
    ans += 1


for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N):
        if not prime[q] or p == q:
            continue
        if count(q) < 4:
            break
        for r in range(q+1, N+1):
            if not prime[r] or p == r:
                continue
            if count(r) < 4:
                break
            ans += 1


for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 4:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 14:
            break
        ans += 1


for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 24:
            break
        ans += 1

print(ans)

Solution (Python):
n = int(input())
from sys import exit
if n == 1:
  print(0)
  exit()

from collections import defaultdict as dd
dic_list = [{}, {}, {2: 1}]
def prime_factrization(num):  
  dic = dd(lambda: 0)
  for i in range(2, int(num**0.5) + 2):
    mod = num % i
    while mod == 0:
      num //= i
      dic[i] += 1
      mod = num % i
    if num == 1:
      break
  else:
    if num != 1:
      dic[num] += 1
  return dic

dic = dd(lambda: 0)
for i in range(2, n+1):
  pf = prime_factrization(i)
  for j in range(2, 100):
    dic[j] += pf[j]



up3_divisor = 0
for num in dic.values():
  if num >= 2:
    up3_divisor += 1
up5_divisor = 0
for num in dic.values():
  if num >= 4:
    up5_divisor += 1
up15_divisor = 0
for num in dic.values():
  if num >= 14:
    up15_divisor += 1
up25_divisor = 0
for num in dic.values():
  if num >= 24:
    up25_divisor += 1
up75_divisor = 0
for num in dic.values():
  if num >= 74:
    up75_divisor += 1

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
if up75_divisor >= 1:
  ans += combinations_count(up75_divisor, 1) 
if up25_divisor >= 1:
  ans += combinations_count(up25_divisor, 1) * (combinations_count(up3_divisor, 1) - 1) 
if up15_divisor >= 1:
  ans += combinations_count(up15_divisor, 1) * (combinations_count(up5_divisor, 1) - 1) 
if up5_divisor >= 2:
  ans += combinations_count(up5_divisor, 2) * (combinations_count(up3_divisor, 1) - 2) 
print(ans)

Solution (Python):





from collections import Counter, defaultdict
from itertools import product

n = int(input())

def prime_factorization(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

prime = []
for i in range(1, n+1):
    prime += prime_factorization(i)
    
ctr = Counter(prime)


d = defaultdict(list)
for k, v in ctr.items():
    for p in [2, 4, 14, 24, 74]:
        if v >= p:
            d[p].append(k)
        else:
            break

            

comb_num = 0
for comb in [[2, 4, 4], [4, 14], [2, 24], [74]]:
    for prime_comb in list(product(*[d[c] for c in comb])):
        if len(prime_comb) != len(set(prime_comb)):
            continue
        if comb == [2, 4, 4] and prime_comb[1] < prime_comb[2]:
            continue
        comb_num += 1
print(comb_num)

Solution (Python):
import numpy as np
from itertools import combinations
U = 101
T = np.zeros(U,np.int32)
T[2] = 1
T[3::2] = 1
for i in range(U):
  if i*i>U:
    break
  if T[i]==1:
    T[i*i::2*i] = 0
N = int(input())
pls = np.where(T)[0].tolist()
dic = {}
for i in range(1,N+1):
  for p in pls:
    cnt = 0
    while i%p==0:
      i //= p
      cnt += 1
    dic[p] = dic.get(p,0)+cnt
ans = 0
for a,b,c in combinations(pls,3):
  if 2<=dic[a] and 4<=dic[b] and 4<=dic[c]:
    ans += 1
  if 4<=dic[a] and 2<=dic[b] and 4<=dic[c]:
    ans += 1
  if 4<=dic[a] and 4<=dic[b] and 2<=dic[c]:
    ans += 1
for a, b in combinations(pls,2):
  if 4<=dic[a] and 14<=dic[b]:
    ans += 1
  if 14<=dic[a] and 4<=dic[b]:
    ans += 1
  if 2<=dic[a] and 24<=dic[b]:
    ans += 1
  if 24<=dic[a] and 2<=dic[b]:
    ans += 1

for a in pls:
  if 74<=dic[a]:
    ans += 1
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import permutations as p

def factorize(n):
    d = defaultdict(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = Counter()
for i in range(1, N+1):
    d += factorize(i)
vl = d.values()

ans = sum(1 for i, j, k in p(vl, 3) if i>=2 and j>=4 and k>=4)//2
ans += sum(1 for i, j in p(vl, 2) if i>=2 and j>=24)
ans += sum(1 for i, j in p(vl, 2) if i>=4 and j>=14)
ans += sum(1 for i in vl if i>=74)
print(ans)

Solution (Python):
from collections import defaultdict as dd
from itertools import permutations as p

def factorize(n):
    d = dd(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = dd(int)
for i in range(1, N+1):
    e = factorize(i)
    for i,j in e.items():
        d[i] += j
vl = d.values()

ans = sum(1 for i, j, k in p(vl, 3) if i>=2 and j>=4 and k>=4)//2
ans += sum(1 for i, j in p(vl, 2) if i>=2 and j>=24)
ans += sum(1 for i, j in p(vl, 2) if i>=4 and j>=14)
ans += sum(1 for i in vl if i>=74)
print(ans)

Solution (Python):
from collections import defaultdict as dd
from itertools import permutations as p

def factorize(n):
    d = dd(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = dd(int)
for i in range(1, N+1):
    e = factorize(i)
    for i,j in e.items():
        d[i] += j

ans = 0
for i, j, k in p(d.values(), 3):    
    if i>=2 and j>=4 and k>=4:
        ans += 1
ans //= 2

for i, j in p(d.values(), 2):
    if i>=2 and j>=24:
        ans += 1
    if i>=4 and j>=14:
        ans += 1

for i in d.values():
    if i>=74:
        ans += 1

print(ans)

Solution (Python):
N=int(input())
pr=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
l=[0]*15
for i in range(1,N+1):
    for j in range(15):
        while 1:
            if i%pr[j]==0:
                i//=pr[j]
                l[j]+=1
            else:
                break
a,b,c,d,e=0,0,0,0,0
for i in l:
    if i>=2:
        a+=1
    if i>=4:
        b+=1
    if i>=14:
        c+=1
    if i>=24:
        d+=1
    if i>=74:
        e+=1
print((a-2)*b*(b-1)//2+c*(b-1)+d*(a-1)+e)

Solution (Python):
n = int(input())
primes = [0 for i in range(n+1)]
for i in range(2,n+1):
    cur = i
    for j in range(2,i+1):
        while cur % j == 0:
            cur = cur // j
            primes[j] += 1
def num(m):
    res = 0
    for i in primes:
        if i >= m-1:
            res += 1
    return res
print(num(75) + (num(5) - 1) * num(5) * (num(3) - 2) // 2
 + num(15) * (num(5) - 1) + num(25) * (num(3) - 1) )

Solution (Python):
from scipy.misc import comb

def prime_factorize_dict(N):
    d = dict()
    for n in range(2, N + 1):
        while not n & 1:
            d[2] = d.get(2, 0) + 1
            n >>= 1
        f = 3
        while f * f <= n:
            if not n % f:
                d[f] = d.get(f, 0) + 1
                n //= f
            else:
                f += 2
        if n != 1:
            d[n] = d.get(n, 0) + 1
    return {k:v for k, v in d.items() if v > 1}

d = prime_factorize_dict(int(input()))

l = [0] * 5
for p, k in d.items():
    if k < 4:
        index = 0
    elif k < 14:
        index = 1
    elif k < 24:
        index = 2
    elif k < 74:
        index = 3
    else:
        index = 4
    l[index] += 1


total = l[0] * comb(sum(l[1:]), 2, exact=True) + comb(sum(l[1:]), 3, exact=True) * 3

total += l[1] * sum(l[2:]) + comb(sum(l[2:]), 2, exact=True) * 2

total += sum(l[0:3]) * sum(l[3:]) + comb(sum(l[3:]), 2, exact=True) * 2

total += l[4]

print(total)

Solution (Python):

N=int(input())
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

def Count(x):
    res=0
    tmp=N
    while tmp//x:
        tmp=tmp//x
        res+=tmp
    return res

cnt=[Count(p) for p in prime]

def Sum(n):
    return sum([x>=n for x in cnt])

Ans=0
Ans=Sum(74)+Sum(24)*(Sum(2)-1)+Sum(14)*(Sum(4)-1)+Sum(4)*(Sum(4)-1)*(Sum(2)-2)//2
print(Ans)

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

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

def f(x):
    return sum(exponent >= x - 1 for exponent in exponents)

ans = 0
ans += f(75)
ans += f(25) * (f(3) - 1)
ans += f(15) * (f(5) - 1)
ans += f(5) * (f(5) - 1) // 2 * (f(3) - 2)

print(ans)

Solution (Python):
import math
def C(a,b):
    if a < b:
        return 0
    else:
        return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

N = int(input())
if N == 1:
    print(0)

else:
    PF = dict()
    for i in range(2, N+1):
        n = i
        for x in PF.keys():
            while n % x == 0:
                n //= x
                PF[x] += 1
        if n != 1:
            PF[n] = 1
    
    count, number = [0]*5, [3, 5, 15, 25, 75]
    for x in PF.values():
        for i in range(5)[::-1]:
            if x + 1 >= number[i]:
                count[i] += 1
                break
    ans = 0
    ans += C(count[0], 1) * C(sum(count[1:]), 2) + 3 * C(sum(count[1:]), 3)
    ans += C(count[1], 1) * C(sum(count[2:]), 1) + 2 *C(sum(count[2:]), 2)
    ans += C(sum(count[:3]), 1) * C(sum(count[3:]), 1) + 2 * C(sum(count[3:]), 2)
    ans += count[4]
    print(ans)

Solution (Python):
import math

N = int(input())

prime = [0 for _ in range(47 + 1)]
lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

for i in range(2, N + 1):
	num = i
	
	for p in lst:
		while True:
			if num % p == 0:
				num //= p
				prime[p] += 1
			else: break
			if num == 1: break
		

_75 = 0
_25 = 0
_15 = 0
_5 = 0
_3 = 0

for i in range(len(prime)):
	if prime[i] >= 2:
		_3 += 1
	if prime[i] >= 4:
		_5 += 1
	if prime[i] >= 14:
		_15 += 1
	if prime[i] >= 24:
		_25 += 1
	if prime[i] >= 74:
		_75 += 1
		
def comb(a, b):
	return math.factorial(a) / (math.factorial(b) * math.factorial(a - b))
		
ans = 0
ans += _75
ans += (_3 - 1) * _25 
ans += (_5 - 1) * _15
if _5 >= 2:
	ans += (_3 - 2) * comb(_5, 2)

print(int(ans))

Solution (Python):
def fac_count( x, counter):
    i=2;
    while x > 1:
        if x%i == 0:
            counter[i] = counter.get(i,0) + 1
            x //= i
        else:
            i += 1
    return counter

n=int(input())
counter = {}
for i in range(2,n+1):
    counter = fac_count(i,counter)

fac = [0] * 5 

for i in counter.values():
    if i>=2:  fac[0] += 1
    if i>=4:  fac[1] += 1
    if i>=14: fac[2] += 1
    if i>=24: fac[3] += 1
    if i>=74: fac[4] += 1

 
ans =   fac[1] * (fac[1]-1)//2 * (fac[0]-2) + fac[3] * (fac[0] - 1) + fac[2] * (fac[1] - 1) + fac[4]
print(ans)