Project Euler Problem 5-Smallest multiple

对每个数字分解素因子，最后对每个素因子去其最大的指数，然后把不同素因子的最大指数次幂相乘，得到的就是最小公倍数

python不熟练，代码比较挫

mp = {}

def process(n):

    i = 2

    while i*i <= n:

        cnt = 0

        if n%i == 0:

            while n%i == 0:

                cnt += 1

                n /= i

            if i in mp:

                mp[i] = max(mp[i], cnt)

            else:

                mp[i] = cnt

        i += 1

    if n > 1:

        if n in mp:

            mp[n] = max(mp[n], 1)

        else:

            mp[n] = 1

for i in range(2,21):

    process(i)

res = 1

for x in mp:

    res *= (x**mp[x])

print res

巴特西

Project Euler Problem 5-Smallest multiple

最新文章

热门文章