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



Sample input:
9


Sample output:
0

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heapreplace
from itertools import count, product, combinations
from functools import partial, reduce
from math import floor, ceil, sqrt
from collections import defaultdict, deque

def Primes_fnct():
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in [0]*search_range[1].bit_length():
            update_range(sum(search_range)//2)
        return search_range[0]
    
    P = [2,]
    Pappend = P.append
    Q = deque([])
    Qappend = Q.append
    Qpopleft = Q.popleft
    hq = [] 
    integer = count(3,2)
    current_i = 1
    valid_range = 1
    def Primes(*, max_int=None):
        nonlocal valid_range, current_i
        if max_int is None:
            return P[:]

        if  max_int - current_i <= 1:
            return P[:b_search(P,max_int)+1]

        for i in integer:
            if i >= valid_range:
                if Q:
                    q = Qpopleft()
                    heappush(hq, (q**2,q))
                valid_range = Q[0]**2 if Q else i**2

            m,r = hq[0] if hq else (0,0)
            if i != m:
                Pappend(i)
                Qappend(i)

            while m == i:
                heapreplace(hq, (m+2*r, r))
                m,r = hq[0]

            current_i = i
            if max_int - current_i <=1:
                break 
        return P[:]
    return Primes

def factorization(m, Primes=None):
    F = defaultdict(int)
    if m < 2:
        return F

    while not m&1:
        F[2] += 1
        m >>= 1

    if Primes is None:
        Primes = Primes_fnct()

    Primes = deque(Primes(max_int=ceil(sqrt(m))+1))
    Primespopleft = Primes.popleft

    while m > 1 and Primes:
        p = Primespopleft()
        while not m%p:
            m //= p
            F[p] += 1

    if m > 1:
        F[m] += 1
    return F

def solve():
    N = int(input())
    Primes = Primes_fnct()
    F = defaultdict(int)
    for i in range(1,N+1):
        f = factorization(i)
        for k in f.keys():
            F[k] += f[k]
    P = defaultdict(set)
    for k in F.keys():
        for n in (2,4,14,24,74):
            if F[k] >= n:
                P[n] = P[n]|{k,}
    res = 0
    for Q in (((2,1),(4,2)), ((2,1),(24,1)), ((4,1),(14,1)), ((74,1),)):
        R = set()
        if all(len(P[q[0]]) >= q[1] for q in Q):
            for r in product(*(combinations(P[q[0]],q[1]) for q in Q)):
                r_ = [i for j in r for i in j]
                if len(r_) == len(set(r_)):
                    R |= {r,}
        res += len(R)

    return res



if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
if N <= 9:
    print(0)
    exit()

def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = Counter()
for n in range(2,N+1):
    factors += factorize(n)


# 5-5-3
four = two = 0
for v in factors.values():
    if v >= 2:
        two += 1
    if v >= 4:
        four += 1
ans = four*(four-1)//2
two -= 2
ans *= two

# 15-5
d14 = d4 = 0
for v in factors.values():
    if v >= 4:
        d4 += 1
    if v >= 14:
        d14 += 1
ans += d14 * (d4-1)

# 25-3
d24 = d2 = 0
for v in factors.values():
    if v >= 2:
        d2 += 1
    if v >= 24:
        d24 += 1
ans += d24 * (d2-1)

# 75
d74 = 0
for v in factors.values():
    if v >= 74:
        d74 += 1
ans += d74

print(ans)

Submission status: Accepted

Solution code:
#from scipy.misc import comb
N = int(input())

if N <= 9:
  print(0)
  exit(0)
  
P = {}
for i in range(2,N+1):
  work = i
  for j in range(2,i+1):
    while work % j == 0:
      if not j in P:
        P[j] = 1
      else:
        P[j] += 1
      work = work // j
      #print(work,j,i)
    if work == 1:
      break
      
#(74)(24,2)と(14,4)と(4,4,2)が取れればそれが答え
# a:2, b:4, c:14, d:24, e:74
a,b,c,d,e = 0,0,0,0,0
for k,v in P.items():
  if v >= 2:
    a += 1
  if v >= 4:
    b += 1
  if v >= 14:
    c += 1
  if v >= 24:
    d += 1
  if v >= 74:
    e += 1
#print(P)
#print(a,b,c,d,e)
print(b*(b-1)*(a-2) // 2 + (c * (b-1) if b > 0 else 0) + (d * (a-1) if a > 0 else 0) + e)

Submission status: Accepted

Solution code:
N=int(input())
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]
Pdict=dict()
D=dict()
X=[0 for i in range(25)]
for i in range(25):
    D[Prime[i]]=0
    Pdict[Prime[i]]=i
for i in range(1,N+1):
    k=i
    for p in Prime:
        while(True):
            if k%p==0:
                k=k//p
                D[p]+=1
            else:
                break
for i in range(25):
    X[i]=D[Prime[i]]
ans=0
for i in range(25):
    for j in range(25):
        for k in range(25):
            if i==j or j==k or k==i:
                continue
            if X[i]>=4 and X[j]>=4 and X[k]>=2:
                #pi^4*pj^4*pk^2
                if i<j:
                    ans+=1
for i in range(25):
    for j in range(25):
        if i==j:
            continue
        if X[i]>=24 and X[j]>=2:
            #pi^24*pj^2
            ans+=1
for i in range(25):
    for j in range(25):
        if i==j:
            continue
        if X[i]>=14 and X[j]>=4:
            #pi^14*pj^4
            ans+=1
for i in range(25):
    if X[i]>=74:
        #pi^74
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

f = 1
for i in range(1,n+1):
    f *= i

ps = [0 for i in range(101)]
for i in range(2,100):
    while f % i == 0:
        f //= i
        ps[i] += 1

ans = 0
for i1 in range(0,100):
    for i2 in range(0,100):
        for i3 in range(i2+1,100):
            if i1 == i2 or i1 == i3: continue
            if (ps[i1]+1) >= 3 and (ps[i2]+1) >= 5 and (ps[i3]+1) >= 5:
                ans += 1
for i1 in range(0,100):
    for i2 in range(0,100):
        if i1 == i2: continue
        if (ps[i1]+1) >= 3 and (ps[i2]+1) >= 25:
            ans += 1
        if (ps[i1]+1) >= 15 and (ps[i2]+1) >= 5:
            ans += 1
            
for i1 in range(0,100):
    if (ps[i1]+1) >= 75:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
ps = [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())
primes = {}
for i in range(2,N+1):
    n = i
    for j in range(25):
        if n==1 or n<ps[j]:break
        while n%ps[j]==0:
            if ps[j] in primes.keys():
                primes[ps[j]]+=1  
            else:
                primes[ps[j]]=1
            n //= ps[j]
#print(primes)
#3,5,5
#3,25
#5,15
#75
three = len([v for v in primes.values() if v>=3-1])
five = len([v for v in primes.values() if v>=5-1])
fift = len([v for v in primes.values() if v>=15-1])
twfiv = len([v for v in primes.values() if v>=25-1])
sevfiv = len([v for v in primes.values() if v>=75-1])
print(five*(five-1)//2*(three-2) + twfiv*(three-1) + fift*(five-1) + sevfiv)

Submission status: Accepted

Solution code:
n = int(input())

from collections import defaultdict
from math import sqrt

A = defaultdict(int)

def factorize(n):    
    i = 2
    
    while n % i == 0:
        n //= i
        A[i] += 1
    i += 1

    while n != 1 and i <= sqrt(n):
        while n % i == 0:
            n //= i
            A[i] += 1
        i += 2
    if n != 1:
        A[n] += 1

    return A

for i in range(1, n+1):
    factorize(i)

ans = 0

c_74 = 0
c_2 = 0
c_24 = 0
c_4 = 0
c_14 = 0

for k, v in A.items():
    if v >= 74:
        c_74 += 1
    if v >= 2:
        c_2 += 1
    if v >= 24:
        c_24 += 1
    if v >= 4:
        c_4 += 1
    if v >= 14:
        c_14 += 1

ans += c_74
ans += max(0, (c_2 - 1) * c_24)
ans += max(0, (c_2 - 2) * c_4 * (c_4 - 1) // 2)
ans += max(0, c_14 * (c_4 - 1))

print(ans)

Submission status: Accepted

Solution code:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)

zd = {}

for i in range(2, N+1):
    for j in range(2,N+1):
        while i%j==0:
            if j not in zd:
                zd[j] = 0
            zd[j]+=1
            i = i//j
z1 = []
for x in zd:
    if zd[x]>=2:
        z1.append(zd[x])
dprint(z1)
re = 0
def search(ki, zt, ti):
    if ti>=len(zt):
        global re
        re+=1
        return
    global z1
    if ki >= len(z1):
        return
    search(ki+1, zt,ti)
    if z1[ki] +1 >= zt[ti]:
        search(ki+1, zt,ti+1)

search(0, [75,], 0)
search(0, [3,25], 0)
search(0, [25,3], 0)
search(0, [15,5], 0)
search(0, [5,15], 0)
search(0, [3,5, 5], 0)
search(0, [5,3, 5], 0)
search(0, [5,5, 3], 0)


print(re)

Submission status: Accepted

Solution code:
def prf(m):
    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
    return pf

from collections import defaultdict
Pr = defaultdict(lambda: 1)

m = int(input())
for i in range(1,m+1):
    j = prf(i)
    for k, l in j.items():
        Pr[k] += l
A = list(Pr.values())
a3 = sum([True for i in A if i == 3 or i == 4])
a5 = sum([True for i in A if i >= 5])
a15 = sum([True for i in A if i >= 15])
a25 = sum([True for i in A if i >= 25])
a75 = sum([True for i in A if i >= 75])
ans = a3*a5*(a5-1)//2 + a5*(a5-1)*(a5-2)//2 + (a5-a15)*a15 + a15*(a15-1) \
+ (a3+a5-a25)*a25 + a25*(a25-1) + a75
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
N=int(input())
if N<=5:
    print(0)
    sys.exit()

z=100
Combi=[[] for i in range(z+1)]
Combi[0]=[1,0]

for i in range(1,z+1):
    Combi[i].append(1)
    for j in range(i):
        Combi[i].append(Combi[i-1][j]+Combi[i-1][j+1])
    Combi[i].append(0)

    
FACT=dict()


for x in range(2,N+1):
    L=math.floor(math.sqrt(x))
    
    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

LIST=[list(FACT.values())[i] for i in range(len(FACT)) if FACT[list(FACT.keys())[i]]>=2]

x2=len([l for l in LIST if l>=2])
x4=len([l for l in LIST if l>=4])
x24=len([l for l in LIST if l>=24])
x14=len([l for l in LIST if l>=14])
x74=len([l for l in LIST if l>=74])

ANS1=(x2-2)*Combi[x4][2]
ANS2=x24*(x2-1)
ANS3=x14*(x4-1)
ANS4=x74

print(ANS1+ANS2+ANS3+ANS4)

Submission status: Accepted

Solution code:
N = input()
C = [0]*101
for i in range(1, N+1):
  f = 2
  while i>1:
    if i%f==0:
      C[f] += 1
      i /= f
    else:
      f += 1
ans = 0
for i in range(101):
  if C[i]>=2:
    for j in range(101):
      if j != i and C[j]>=4:
        for k in range(j):
          if k != i and C[k]>=4:
            ans += 1
for i in range(101):
  if C[i]>=2:
    for j in range(101):
      if j != i and C[j]>=24:
        ans += 1
for i in range(101):
  if C[i]>=14:
    for j in range(101):
      if j != i and C[j]>=4:
        ans += 1
for i in range(101):
  if C[i]>=74:
    ans += 1
print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

def main():
    n = I()
    d = collections.defaultdict(int)
    pr = Prime(10000)
    r = 0

    for i in range(2,n+1):
        t = pr.division(i)
        for k,v in t:
            d[k] += v
    c = collections.defaultdict(int)
    for k,v in d.items():
        if v >= 74:
            c[75] += 1
        if v >= 24:
          c[25] += 1
        if v >= 14:
          c[15] += 1
        if v >= 4:
          c[5] += 1
        if v >= 2:
            c[3] += 1

    r += c[75]
    r += c[25] * (c[3]-1)
    r += c[15] * (c[5]-1)
    if c[5] > 1:
        r += c[5] * (c[5]-1) // 2 * (c[3]-2)


    return r


print(main())

Submission status: Accepted

Solution code:
N = int(input())
D = {}
for x in range(2, N+1):
    y = 2
    while y*y <= x:
        if x % y == 0:
            c = 0
            while x % y == 0:
                x //= y
                c += 1
            D[y] = D.get(y, 0) + c
        y += 1
    if x > 1:
        D[x] = D.get(x, 0) + 1

*P, = D.items()
M = len(P)
memo = {}
def dfs(i, c):
    key = (i, c)
    if key in memo:
        return memo[key]
    if c == 75:
        return 1
    if i == M:
        return 0
    k, v = P[i]
    r = 0
    for j in range(v+1):
        if c*(j+1) <= 75:
            r += dfs(i+1, c*(j+1))
    memo[key] = r
    return r
print(dfs(0, 1))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
primes = []

for i in range(2, n+1):
    ok = True
    for j in range(2, i):
        if i % j == 0:
            ok = False
            break
    if ok:
        primes.append(i)

es = []
for p in primes:
    k = n//p
    e = 0
    while k > 0:
        e += k
        k //= p
    es.append(e)
# print(es)

# 3*5*5
# 15*5
# 25*3
# 75

m = len(es)

ct = 0
for i in range(m):
    for j in range(i+1, m):
        for k in range(m):
            if i != k and j != k and es[i] >= 4 and es[j] >= 4 and es[k] >= 2:
                ct += 1

for i in range(m):
    for j in range(m):
        if i != j and es[i] >= 14 and es[j] >= 4:
            ct += 1

for i in range(m):
    for j in range(m):
        if i != j and es[i] >= 24 and es[j] >= 2:
            ct += 1

for i in range(m):
    if es[i] >= 74:
        ct += 1

print(ct)

Submission status: Runtime Error

Solution code:
N = int(input())

fact_ct = [0 for _ in range(N+1)]
pr = []

def primes():
  ans = set()
  visited = set()
  for p in range(2,N+1):
    if p in visited:
      continue
    ans.add(p)
    q = p
    while q <= N:
      visited.add(q)
      q += p
    
def add_fact_ct(n):
  visited = set()
  for p in range(2,N+1):
    if p not in pr:
      continue
    while n % p == 0:
      fact_ct[p] += 1
      n //= p 
    n //= p
  
pr = primes() 
for n in range(2, N+1):
  add_fact_ct(n)
  
ct_75 = 0
ct_25 = 0
ct_15 = 0
ct_5 = 0
ct_3 = 0
ct_1 = 0
  
for ct in fact_ct:
  if ct >= 75:
    ct_75 += 1
  if ct >= 25:
    ct_25 += 1
  if ct >= 15:
    ct_15 += 1
  if ct >= 5:
    ct_5 += 1 
  if ct >= 3:
    ct_3 += 1
  if ct >= 1:
    ct_1 += 1

ans = 0

ans += ct_75 * (ct_1-1)
ans += ct_25 * (ct_3-1)
ans += ct_15 * (ct_5-1)

print(ans)

Submission status: Runtime Error

Solution code:

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

n=int(input())
primes=primesbelow(n)
factor={}

def val(n,d):
    ans=0
    t=d
    while(t<=n):
        ans+=(n//t)
        t*=d
    return ans
g2=0
g4=0
g24=0
g14=0
g74=0
for i in primes:
    k=val(n,i)
    if k>=4:
        g4+=1
    if k>=2:
        g2+=1
    if k>=24:
        g24+=1
    if k>=14:
        g14+=1
    if k>=74:
        g74+=1

a=(g2-2)*((g4*(g4-1))//2)
b=g24*(g2-1)
c=g14*(g4-1)
d=g74
print(a+b+c+d)

Submission status: Runtime Error

Solution code:
# from collections import Counter
from copy import deepcopy

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

N = int(input())
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]
dp = [[0] * 26 for _ in range(N)]
if N == 1:
    print(0)
else:
    for i in range(1,N):
        dp[i] = deepcopy(dp[i-1])
        temp = Counter(prime_factorize(i+1))
        for x in temp.items():
            if len(prime_factorize(x[0])) == 1:
                dp[i][prime.index(x[0])] += x[1]
        four = 0
        two = 0
        fourteen = 0
        twenty_four = 0
        seventy_four = 0
        for j in range(25):
            if dp[i][j] >= 74:
                seventy_four += 1
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 24:
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 14:
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 4:
                four += 1
                two += 1
            elif dp[i][j] >= 2:
                two += 1
        dp[i][25] = ((four*(four-1))//2) * (two-2) + twenty_four * (two-1) + fourteen * (four-1) + seventy_four
    print(dp[N-1][25])

Submission status: Runtime Error

Solution code:
from collections import Counter
N=int(input())
p=[]
dp=[[0]*100 for _ in range(100)]
dp[0][1]=1

for i in range(2,N+1):
    ti=i
    for j in range(2,i+1):
        while ti%j==0:
            p.append(j)
            ti//=j

cnt=Counter(p)

for i,v in enumerate(cnt.values()):
    for j in range(100):
        for k in range(1,v+2):
            dp[i+1][min(76,j*k)]+=dp[i][j]
    ans=dp[i+1][75]

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())

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

def num(k):
  ret=0
  for i in range(n):
    if e[i]>=k:
      ret += 1
print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
d=[0]*101
def factorization(n):
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i==0:
            while temp%i==0:
                d[i]+=1
                temp //= i
    if temp!=1:
        d[temp]+=1
def cnt(k):
    return len(d[d>=k])
for i in range(2,n+1):
    factorization(i)
d=np.array(list(d.values()))
print(cnt(74)+cnt(24)*(cnt(2)-1)+cnt(14)*(cnt(4)-1)+cnt(4)*(cnt(4)-1)*(cnt(2)-2)//2)

Submission status: Runtime Error

Solution code:
def is_prime(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def prime_factor(n):
    if n == 1:
        return {1: 1}

    pf = dict()
    r = list(range(2, n + 1))

    while n != 1:
        x = r[0]
        cnt = 0
        while n % x == 0:
            n = n // x
            cnt += 1
        if cnt > 0:
            pf[x] = cnt
        r = list(filter(lambda y: y % x != 0, r))

    return pf


def main():
    from fractions import factorial as f
    from collections import defaultdict
    n = int(input())
    d = defaultdict(int)
    for i in range(1, n + 1):
        p = prime_factor(i)
        for k, v in p.items():
            d[k] += v
    
    f2_, f4_, f14_, f24_, f74_ = 0, 0, 0, 0, 0
    for i in d.values():
        if i >= 2:
            f2_ += 1
        if i >= 4:
            f4_ += 1
        if i >= 14:
            f14_ += 1
        if i >= 24:
            f24_ += 1
        if i >= 74:
            f74_ += 1

    ans = f74_ + f24_ * (f2_ - 1) + f14_ * (f4_ - 1) + f4_ * (f4_ - 1) * (f2_ - 2) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    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())
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def f(n):
    # prime factorization of n!
    pf = [0 for _ in range(2, n + 1)]
    for i in range(1, n + 1):
        cur = i
        for j in range(2, i + 1):
            while cur % j == 0:
                pf[j] += 1
                cur //= j
    return pf


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


def main():
    N = int(input())
    pf = f(N)
    ans = num(75, pf)
    ans += num(25, pf) * (num(3, pf) - 1)
    ans += num(15, pf) * (num(5, pf) - 1)
    ans += num(5, pf) * (num(5, pf) - 1) * (num(3, pf) - 2) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    h = list(map(int, input().split()))

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

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

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num, dict_counter):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    dict_counter = {}
    for i in range(1, N+1):
        prime_factorization_2(i, dict_counter)

    l = list(dict_counter.values())
    ll = len(l)

    cnt=0
    for i in range(ll-2):
        for j in range(i+1,ll-1):
            for k in range(j+1,ll):
                if (l[i]>=4 and l[j]>=4 and l[k]>=2) or (l[i]>=4 and l[j]>=2 and l[k]>=4) or (l[i]>=2 and l[j]>=4 and l[k]>=4):
                    cnt+=1
    
    for i in range(ll-1):
        for j in range(i+1,ll):
            if (l[i]>=4 and l[j]>=14) or (l[i]>=14 and l[j]>=4):
                cnt+=1
            if (l[i]>=24 and l[j]>=2) or (l[i]>=2 and l[j]>=24):
                cnt+=1
    
    for i in range(ll):
        if l[i]>=54:
            cnt+=1
    print(cnt)
                


    


# resolve()


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """9"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100"""
        output = """543"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()