算法1

(线性筛法) $O(n)$

python 代码

from math import gcd,factorial
# from heapq import merge
# import sys
from sys import stdin


def get_prime(x):
    cnt = 0
    for i in range(2,x+1):
        if not st[i]:
            prime[cnt] = i
            minp[i] = i
            cnt += 1
        for j in range(cnt):
            ans = i*prime[j]
            if ans > x:
                break
            st[ans] = True
            minp[ans] = prime[j]
            if i % prime[j] == 0:
                break


if __name__ == "__main__":
    # num = list(map(int, sys.stdin.readlines()))
    prime = [0 for i in range(1000000)]
    minp = [0 for i in range(1200000)]
    st = [False for i in range(1200000)]
    get_prime(1024*1024)
    for x in stdin:
        x = int(x)
        tol = 0
        cnt = 0
        sum = [0 for i in range(1000)]
        while x>1:
            p = minp[x]
            while(x%p == 0):
                x = x//p
                sum[cnt] += 1
                tol += 1
            cnt += 1
        all_s = 1
        for i in range(cnt):
            all_s *=factorial(sum[i])
        print(tol, factorial(tol)//(all_s))