Problem:


Score : 300 points

Problem Statement

You are given an integer N.
Find the number of the positive divisors of N!, modulo 10^9+7.

Constraints

1≤N≤10^3

Input

The input is given from Standard Input in the following format:

N

Output

Print the number of the positive divisors of N!, modulo 10^9+7.

Sample Input 1

3

Sample Output 1

4

There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.

Sample Input 2

6

Sample Output 2

30

Sample Input 3

1000

Sample Output 3

972926972



Sample input:
3


Sample output:
4

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
divisor = [[i,0] for i in range(n+1)]


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

for i in range(2,n+1):
    lst = factorization(i)
    for l in lst:
        divisor[l[0]][1] += l[1]

ans = 1
for d in divisor:
    if d[1] != 0:
        ans *= (d[1] + 1)
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def factor(n):
    for i in range(2, n+1):
        if n % i == 0:
            l = factor(n // i)
            l.append(i)
            return l
    return []

from collections import Counter
N = int(input())
c = Counter()
for i in range(1, N+1):
    c += Counter(factor(i))
p = 1
for _, i in c.items():
    p *= (i+1)
    p %= 1000000007
print(p)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

MOD = 1000000007  # type: int

def is_prime(n):
    if n == 1: return False

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

    return True

def solve(N: int):
    primes = [n for n in range(1, N+1) if is_prime(n)]
    counter = [0] * len(primes)
    for n in range(2, N+1):
        for i, p in enumerate(primes):
            mod = 0
            c = 0
            r = n
            while(mod == 0):
                mod = r % p
                r /= p
                if mod == 0:
                    c += 1
            counter[i] += c
    res = 1
    for c in counter:
        res *= (c+1)
        res %= MOD
    print(res)
    return 


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
p_numbers = [2]
p_dict = {}
for num in range(3, N+1):
  is_prime = True
  for p_num in p_numbers:
    if num%p_num == 0:
      is_prime = False
      break
  if is_prime:
    p_numbers.append(num)
for num in range(1, N+1):
  for prime in p_numbers:
    div = num
    while True:
      if div%prime == 0:
        if prime in p_dict:
          p_dict[prime] += 1
        else:
          p_dict[prime] = 1
      else:
        break
      div = div//prime
ans = 1
for value in p_dict.values():
  ans *= (value+1)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from sys import stdin
from math import sqrt
from collections import defaultdict

MOD = 1000000007
def is_prime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= sqrt(x):
        if x % i == 0:
            return False
        i = i + 2
    
    return True


N = int(stdin.readline().rstrip())
primes = []
for i in range(2, N+1):
    if is_prime(i):
        primes.append(i)

dic = defaultdict()
for i in primes:
    dic[i] = 0

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

ans = 1
for i in primes:
    ans *= (1+dic[i])

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())
p = 10**9+7
cnt = [0 for i in range(n+1)]


def cnt_factor(n):
    i = 2
    k = n
    while i <= n:
        if k % i == 0:
            k = k // i
            cnt[i] += 1
        else:
            i += 1

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


ans = 1
for i in range(2, n+1):
    ans *= (cnt[i]+1) % p

print(ans % p)

Submission status: Accepted

Solution code:
import math
N = int(input())
plist = [2]
for i in range(3, N + 1):
    for prime in plist:
        if i % prime == 0:
            break
    else:
        plist.append(i)
ans = 1
for prime in plist:
    s = 0
    for i in range(1, int(math.log(N, prime)) + 1):
        s += N // (prime ** i)
    ans = ans * (s + 1) % (10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
mod = int(1E9+7)

def prime(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if n != 1:
        factor.append(n)
    return factor

def main():
    P = [0 for _ in range(N+1)]
    for n in range(2, N+1):
        A = prime(n)
        for a in A:
            P[a] += 1

    ans = 1
    for p in P:
        ans =  ans * (p+1) % mod

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
l=[2]
for i in range(3,n+1):
    for p in l:
        if i%p==0:break
    else: l.append(i)
a=1
for p in l:
    s=0
    for i in range(1,int(math.log(n,p))+1):
        s+=n//p**i
    a=a*(s+1)%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
import math

n = int(input())

prime_n = [2]

for i in range(3,n+1,2):
    if all( i % prime != 0 for prime in prime_n):
        prime_n.append(i)

multiply = []

for i in prime_n:
    k = 1
    temp = 0
    while i**k <= n:
        temp += math.floor(n/(i**k))
        k+=1
    
    multiply.append(temp)

ans = 1

for i in multiply:
    ans*=(i+1)
    ans%=((10**9)+7)

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
import sys

def soinsuu(soinsuu_dic, num):
    for i in range(2, int(num ** 0.5) + 1):
        while num % i == 0:
            num //= i
            soinsuu_dic[i] += 1
    if num > 1:
        soinsuu_dic[num] += 1
    return soinsuu_dic

def main():
    num = int(input())
    soinsuu_dic = defaultdict(int)

    for i in range(2, num + 1):
        soinsuu_dic = soinsuu(soinsuu_dic, i)


    ans = 1
    mod = 10 ** 9 + 7
    for ele, value in soinsuu_dic.items():
        ans *= value + 1
        ans %= mod

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
N = int(input())
g = 10 ** 9 + 7


def mul(a, b):
  return (a * b) % g

d = []
DP = [None for _ in range(N+1)]
DP[0] = [0 for _ in range(N+1)]
ans = DP[0].copy()
for i in range(2, N+1):
  for j in (x for x in d if x * x <= N):
    if i % j == 0:
      DP[i] = DP[j].copy()
      for k in range(1, N+1):
          DP[i][k] += DP[i//j][k]
      break
  else:
    d.append(i)
    DP[i] = DP[0].copy()
    DP[i][i] = 1
  for k in range(1, N+1):
      ans[k] += DP[i][k]

print(reduce(mul, [x + 1 for x in ans[1:N+1]]))

Submission status: Accepted

Solution code:
from functools import reduce
N = int(input())
g = 10 ** 9 + 7


def mul(a, b):
  return (a * b) % g

def adda(a, p1, p2):
    for x in range(len(a)):
        a[x] = p1[x] + p2[x]

d = []
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]
for i in range(2, N+1):
  for j in (x for x in d if x * x <= N):
    if i % j == 0:
      adda(DP[i], DP[j], DP[i//j])
      break
  else:
    d.append(i)
    DP[i][i] = 1
  adda(ans, ans, DP[i])

print(reduce(mul, [x + 1 for x in ans[1:N+1]]))

Submission status: Accepted

Solution code:
from functools import reduce
N = int(input())
g = 10 ** 9 + 7

def add(a, b):
  return (a + b) % g
def mul(a, b):
  return (a * b) % g

def adda(a, p1, p2):
    for x in range(len(a)):
        a[x] = add(p1[x], p2[x])

d = []
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]
for i in range(2, N+1):
  for j in (x for x in d if x * x <= N):
    if i % j == 0:
      adda(DP[i], DP[j], DP[i//j])
      break
  else:
    d.append(i)
    DP[i][i] = 1
  adda(ans, ans, DP[i])

print(reduce(mul, [x + 1 for x in ans[1:N+1]]))

Submission status: Accepted

Solution code:
import math
N = int(input())
Nfact = math.factorial(N)
ans = 1
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
c = factorize(Nfact)
for a,b in c:
  ans *= b+1
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
def prime(n):
    number = [i+2 for i in range(n-1)]
    while len(number) > 0:
        yield min(number)
        number = [x for x in number if x % min(number) != 0]

prime_number = []
for i in prime(n):
    prime_number.append(i)
prime_factor = {}
for i in prime_number:
    prime_factor[i] = 0

for i in range(1, n + 1):
    for j in prime_number:
        if i == 1:
            break
        else:
            while i % j == 0:
                i //= j
                prime_factor[j] += 1
num = 1
for i in prime_factor.values():
    num *= i + 1
    num %= mod
print(num)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c, d = LI()
    print(max(a * b, c * d))
    return

#B
def B():
    _ = II()
    s = S()
    d = {}
    d["I"] = 1
    d["D"] = -1
    ans = 0
    now = 0
    for i in s:
        now += d[i]
        ans = max(ans, now)
    print(ans)
    return

#C
def C():
    def primes2(n):
        """https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188"""
        """ Returns  a list of primes < n """
        sieve = [True] * (n//2)
        for i in range(3,int(n**0.5)+1,2):
            if sieve[i//2]:
                sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
        return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
    n = II()
    prime = primes2(n+1)
    d = []
    for i in prime:
        b = n
        f = 0
        while b:
            b = b // i
            f += b
        d.append(f%mod)
    ans = 1
    for i in d:
        ans *= (i + 1)
        ans %= mod
    print(ans)
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c, d = LI()
    print(max(a * b, c * d))
    return

#B
def B():
    _ = II()
    s = S()
    d = {}
    d["I"] = 1
    d["D"] = -1
    ans = 0
    now = 0
    for i in s:
        now += d[i]
        ans = max(ans, now)
    print(ans)
    return

#C
def C():
    def primes2(n):
        """https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188"""
        """ Returns  a list of primes < n """
        sieve = [True] * (n//2)
        for i in range(3,int(n**0.5)+1,2):
            if sieve[i//2]:
                sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
        return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
    n = II()
    prime = primes2(n+1)
    d = defaultdict(int)
    for i in prime:
        b = n
        while b:
            b = b // i
            d[i] += b
            d[i] %= mod
    ans = 1
    for i in d.values():
        ans *= (i + 1)
        ans %= mod
    print(ans)
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
import math
import collections

def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    factor.append(n)
    return factor

n = int(input())
c = collections.Counter([])
for num in range(2, n+1):
  prime_list = trial_division(num)
  c.update(prime_list)
res = 1
for prime, count in c.most_common():
  if(prime > 1):
    res = res * (count + 1)
print(res % (pow(10,9) + 7))

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=[0]*(n+1)
    ans=1
    for i in range(1,n+1):
        num=i
        for j in range(2,i+1):
            if num%j==0:
                while num>1 and num%j==0:
                    num//=j
                    a[j]+=1

    for i in a:
        ans=ans*(i+1)%(10**9+7)
    print(ans)
    return

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int):
    elms = [0] * (N + 1)
    for i in range(2, N + 1):
        tmp = i
        j = 2
        while j <= i:
            while tmp % j == 0:
                elms[j] += 1
                tmp //= j
            j += 1
    ret = 1
    for e in elms:
        if e > 0:
            ret *= e + 1
            ret %= MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

exp_list = [0]*1010

def prime_factorize(N): 
    exponent = 0
    while N%2 == 0:
        exponent+=1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i != 0: continue
        exponent = 0
        while N%i == 0:
            exponent+=1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    for p,e in factorization:
        exp_list[p] += e

for i in range(2,n+1):
    prime_factorize(i)
#print(exp_list)

MOD = 10**9+7
ans = 1
for i in exp_list:
    ans *= i+1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def c_factors_of_factorial(N, MOD=10**9 + 7):
    from math import factorial
    from functools import reduce
    from operator import mul
    from collections import defaultdict

    def prime_factorization(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    ans = reduce(mul, [v + 1 for v in prime_factorization(factorial(N)).values()])
    return ans % MOD

N = int(input())
print(c_factors_of_factorial(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC52 C

from decimal import Decimal
import math
from collections import defaultdict

mod = 10**9+7
n = int(input())

#エラトステネスの篩
def prime(num):
    if n < 2:
        return []
    p_l = [i for i in range(num+1)]
    p_l[1] = 0
    num_s = math.sqrt(num)

    for p in p_l:
        if p == 0:
            continue
        if p > num_s:
            break

        for np in range(2*p,num,p):
            p_l[np] = 0

    return [p for p in p_l if p != 0]

def make(num):
    if num <= 1:
        return False
    else:
        num_s = math.floor(math.sqrt(num))
        p_l = prime(num_s)

        dict_counter = defaultdict(int)
        for p in p_l:
            while num % p == 0:
                dict_counter[p] += 1
                num //= p
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter

if n == 1:
    print(1)
    quit()

sum = [0]*n
for i in range(2,n+1):
    x = list(make(i).items())
    for j,k in x:
        sum[j-1] += k

ans = 1
for i in sum:
    if i > 0:
        ans *= (i+1)
print(ans % mod)

Submission status: Accepted

Solution code:
def c_factors_of_factorial(N, MOD=10**9 + 7):
    from math import factorial
    from functools import reduce
    from operator import mul
    from collections import defaultdict

    def prime_factorization(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    ans = reduce(mul, [v + 1 for v in prime_factorization(factorial(N)).values()])
    return ans % MOD

N = int(input())
print(c_factors_of_factorial(N))

Submission status: Accepted

Solution code:
import sys
import numpy as np
n=int(input())
mod=10**9+7
if n==1:print(1);sys.exit()
def searchPrimeNum(N):
    max = int(np.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= max:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        searchList = [i for i in searchList if i % tmp != 0]
    primeNum.extend(searchList)
    return primeNum
l=len(searchPrimeNum(n))
plist=searchPrimeNum(n)
cnt=[0]*l
for i in range(l):
  k=1 
  while plist[i]**k<=n:
    cnt[i]+=n//(plist[i]**k)
    k+=1
ans=1
for i in cnt:
  ans=(ans*(i+1))%mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
y = [0]*(N+1)
for i in range(1,N+1):
    M = i
    while M > 1:
        for j in range(2,M+1):
            if M%j == 0:
                M = M//j
                y[j] += 1
                break
ans = 1
for i in y:
    ans = (ans*(i+1))%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
    239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
    331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
    421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
    509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
    613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
    709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
    821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
    919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}


def split_primes(x: int) -> int:
    """
    x <= 1000 (10^3)
    """
    if x in primes:
        return {x: 1}

    exp_dict = {}
    while x != 1:
        for prime in primes:
            if prime not in exp_dict:
                exp_dict[prime] = 0
            if x % prime == 0:
                exp_dict[prime] = exp_dict[prime] + 1
                x = int(x / prime)
                break
    return exp_dict


def main():
    N = int(input())
    mod_target = 10 ** 9 + 7

    exp_dict = {}
    for i in range(2, N + 1):
        n_exp = split_primes(i)
        for new_exp in n_exp:
            exp_dict[new_exp] = n_exp[new_exp] + (
                exp_dict[new_exp] if (new_exp in exp_dict) else 0
            )
    count = 1
    for key in exp_dict:
        count = (count * (exp_dict[key] + 1)) % mod_target
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

mul_num = [1]*(N+1)
#print(mul_num)
for i in range(N,2,-1):
    #print(i)
    for j in range(2,i):
        if i%j==0:
            mul_num[int(i/j)] += mul_num[i]
            mul_num[j] += mul_num[i]
            mul_num[i] =0

#print(mul_num)
ans=1
for i in mul_num[2:]:
    if i>0:
      ans *= (i+1)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
ans = 1
mod = 1000000007

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

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

for i in range(2,n+1):
    if a[i]>0:
        ans *= a[i]+1
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())


#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return 'prime number'
    else:
        factor.append(n)
        return factor

prime_cnt = {}
for i in range(1, N + 1):
  ps = trial_division(i)
  if ps == "prime number":
    ps = [i]
  for d in ps:
    if d == 1:
      continue
    if d in prime_cnt:
      prime_cnt[d] += 1
    else:
      prime_cnt[d] = 1
      
#print(prime_cnt)
  
ans = 1
for d in prime_cnt:
  ans *= prime_cnt[d] + 1
  ans %= 1000000007
  
print(ans)

Submission status: Accepted

Solution code:
##                                    .........
##                      .7>?7n. .(wWWVyyyVyVyyyWWAw-.
##                     J~::::<HyyyyyyyyyyyVyyyyyyyZZuXV<.
##             .?<(((JXF:::::+KW#ZuZyyyyyyZZXZZuuuZOvvrw.?.
##           ,!-vvrwD:;XaJ++jWUWSw_OuVVTV7XzXkzzvo(wrrrrrw+_i 
##         .>.zrrvrd>jdXvvvvrrwWOtrrrwzvvrrrwHkrrrrvrvrvrrvw+?. 
##        .!(rrvrvwXm0vrrwAOrtwRtttrrrrrtttttW0rrrvrvrvrvrrvro.i 
##       .~JrvrrvwVW0<zrwXKtltwRtttttrtrrttttX0rrrvrrvrrvrvrrrw.1
##       <JrrvvvQVWS<czrwWZllOuRttttrtrrtttttXktrvrvrvrrrrZ  (rr/>
##     .<jZ<wrrwHWSwx-JwXKO1lOu$tttrrtrrrrttcJ0rrrrvrwXOltt< .rrw-i
##    .jdvI-jCwXWSrrrvvwW0o(jwZrrOrrrrrzzvrZ>JVtrrrrrtwXOlltrrrrrI,;
##   ,+XHvrvrrdHHvrvvvvZWrttrwKCw<jvuzu>?zz:.JZ=lOroJrtwSllltrvvwrl(.
## .~JZU0rvvvvUWSrrvvzzZStrrrdC1duZZZZZXwuuv<dOllwXrvvrtwklllrrrdRr-> 
##(_7  JrrrrrwHWXrvvzzuuStltOr Jwzzuuuuzzvvv1Izl=lZwrvrtOXOlltrrZ4vI-- 
##     kwyvrrdpKrrvvzzzw0lllZ  (ZttOtrrttttrd>~1==ldOrrrtZklltrrO(kr{>
##    .kdSvvrdWSvvwwuuzdI??1{   z=====llllllw<  1z=lXOrrttXOtlrrr(Rrl(
##    .0d+rrvXWXvwWXuuwOI??v    .z>??????==z$~   ?z=lXOtttdZttrrvzSvw(_
##    .0W(rrvXHXvwWuuwZjVTO=!???<O&x>>+I???d! ..(?79UUUVU6wkrrrrrv0vr>) 
##    .kW(rvvwKXvdWuXw$(z?z       1z1>>zz?1>        1zOvOtrXzuzvvrvrvlt
##    .SW(rrvdWqvwHurd:.I?;     ...~?<<<_<<      ..  _1I(wrdXZuvvrrvv01
##     OWrrrrdWHvwHzwK  1v~.(ggggJ.?!         (<(.JggJ.. .TdKZuzvwkvrXj 
##     .WDzvrdHWwwHzdH.  (MHM###MkTU_         .UTWM##NMMN, ?Huuuw(WvrX( 
##      O>zrrwWHkwHzWW{.dY!jNWML .r_!          !jMd@F  k?Wo juuuIJWvvW(
##        (zrzVWKdMwb.:(% .H@HNM@@N             W@HNMagM. C_,kzzCdWvvfz
##         1wvXWWXHX>_>   .hJHXZWHN             XJWUWWHM:   (Rzz1Hkvw\(-
##          1wdWvHHW<>_    ?U0zzXX=             ,WVCO4y=    ydzZJ 4wd 
##           (wf[?Wr1>(.                ..                 .3JuO\ .SI
##            (Wb zH, .__-_____-                  -__~__.-..~.k2   ,\
##             .4  4WHeo~~~~~~~_.                .~~:~<::~.dqH?     !
##                  4fWTe           .1WW&&&&W1          .(OkP 
##                   4f ,n.         \Y       Y1       .d!.H: 
##                    ?   Wx.        &_    _ 2      .dMK  ?
##                         4 ?a..         ~      ..JWDOq%
##                            (HkMNmx.... ....(&kHP,kk\.K                         
##                          ...?qHNWB:::::::::WHHH-.dK
##                       .J>:jz77<:(C:::::::::O_:~?7f;?3(.
##                    ..z>::::u-~::::~::~:::::(<:::(3::::?-
##                 .,C-::::::<:?x<1+-_~~:~~:(J++?!(3~<:<(J=_<.. 
##               .?   ._1.....~~(z-.._(-1+,.....-J!.._(v!      ?1,
##             .<     !   ?1--...~?iv>___~(T+..J=_(Jv^            <.
##            .=      _       ?7u-((JXJ-((JJZ6+JwY!_      _        (.
##           .}                  ?1&J-:<Z<<<:<+=_        . _.       : 
##           / :   .                 _d7COZW>~           (.  .      ..
##          .: !   (                 .>.~(:d             (~    .    !-
##          (  ~   (                 .z777TT             ..    _   . :
##          :  ~   <_                J<<<<<j_            ._    :   { ( 
##         .   !   >_                >.....({            (_    <  .  (.
##         -   ~   >_               ,~.~..~v)            <     <  ;  .; 
##        .       .>                <..~.._Il            ~     ( .    >
##        .       .~               .>.~..~(Iz                  ( .    ( 
##        <       -~               ,_..~..(>j                  .      . 
##        {       <.               <..~..~(<j.                 ..      _
##                >.               >..~...z:(_                  _      <
##       .        >.              .<.~..~_C(<}                  }      . 
##       _       .~.              .~..~..(>(:>                  }       _
##       :       (~.              ._..~..(<(+>                  >       ~
##       ~       <~_                ??<<!!                      <       .
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())
R = {}
MOD = 10 ** 9 + 7
for i in range(1, N + 1):
  t = prime(i)
  for i in t.keys():
    if i not in R:
      R[i] = t[i]
    else:
      R[i] += t[i]
      
ans = 1
for i in R.values():
  ans = ans * (i + 1) % MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10 ** 9 + 7

pfac = [1] * (N + 1)

for i in range(1, N + 1) :
    j = i
    while j % 2 == 0 :
        j //= 2
        pfac[2] += 1
    
    k = 3
    while j > 1 :
        while j % k == 0 :
            j //= k
            pfac[k] += 1
        k += 2
    
ret = 1
for i in range(2, N + 1) :
    ret *= pfac[i]
    ret %= MOD
    
print(ret)

Submission status: Accepted

Solution code:
def power(x,y):
    if x%y != 0:
        return 0
    else:
        return 1+power(x/y,y)


def main():
    n = int(input())
    prime=[]
    fact = {}
    num_list = [i for i in range(2,n+1)]
    i = 0
    ans = 1
    if n ==1:
        print(ans)
        exit()
    mod = 10**9+7
    while i <=n**0.5:
        i = num_list.pop(0)
        prime.append(i)
        for j in num_list:
            if j%i ==0:
                num_list.remove(j)
    prime = prime + num_list

    for i in range(1,n+1):
        for j in prime:
            if i <j:
                break
            elif j in fact.keys():
                fact[j] += power(i,j)
            else:
                fact[j] = power(i,j)
    for i in fact.values():
        ans *= (i+1)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


N = int(input())

ans = 1

dic = {}
ori = [2]#sosuu

dic[2] = 0

for i in range(998):

    i += 2

    flag = True

    for j in ori:

        if i % j == 0:
            flag = False

    if flag:
        dic[i] = 0
        ori.append(i)


for i in range(N):

    i += 1

    for j in ori:

        cnt = 1

        while True:

            if i % (j ** cnt) != 0:
                break

            cnt += 1

        dic[j] += cnt-1

for i in dic:

    ans *= (dic[i] + 1)

print (ans % ( 10 ** 9 + 7 ))

Submission status: Accepted

Solution code:
n = int(raw_input())
sieve = [True for i in range(n+1)] 
for i in range(2, n+1):
    if sieve[i] == True:
        for j in range(i+i, n+1, i):
            sieve[j] = False
res = 1

for i in range(2, n+1):
    m = 1
    if sieve[i] == False:
        continue
    for j in range(i, n+1):
        j2 = j
        while j2 % i == 0:
            m += 1
            j2 /= i
    res = (res * m) % (10**9+7)
print res

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())

def f(n):
    prime = [i for i in range(2, 1000)]
    
    index = 0
    while True:
        p = prime[index]
        
        prime = [v for v in prime if v == p or v % p != 0]
        index += 1
        
        if len(prime) <= index:
            break
    
    return prime

prime = f(N)

def f2(n):
    l = {}
    
    for v in prime:
        while n % v == 0:
            n = n // v
            if l.get(v) == None:
                l[v] = 0
            l[v] += 1
    return l
            
re = {}

for i in range(2, N + 1):
    for k, v in f2(i).items():
        if re.get(k) == None:
            re[k] = 0
        re[k] += v
        
result = 1
for _, v in re.items():
    result *= v + 1
print(result % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
MOD = 10 ** 9 + 7

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

d = defaultdict(int)
for i in range(1, N + 1):
    for j, v in prime_factor(i).items():
        d[j] += v

ans = 1
for v in d.values():
    ans = ans * (v + 1) % MOD
print(ans)