题解 | #n的阶乘#

快速幂算法

任意一个数都可以写作质数的幂的积

6!=6x5x4x3x2x1=(2x3)x5x(2x2)x3x2=（2^4）x（3^2）x（5^1）

因此要做的就是：1.找到20以内所有质数；2.求出n！所对应的质数的幂；3.用快速幂求解

'''快速幂算法'''
def FastExponentiation(a,b):
    ans=1
    while b!=0:
        if b%2==1:
            ans=ans*a
        b=b//2
        a=a*a
    return ans

while 1:
    try:
        n=int(input())
        primen=[0 for i in range(8)]#存放[2,3,5,...,19]的幂次数
        for i in range(1,n+1):
            j=0
            while i>=prime[j]:
                if i %prime[j]==0:
                    primen[j]+=1
                    i=i//prime[j]
                else:
                    j+=1
        res=1
        for i in range(8):
            res=res*FastExponentiation(prime[i], primen[i])
        print(res)
    except:
        break