美文网首页
codewars刷题之 “Factorial decompos

codewars刷题之 “Factorial decompos

作者: wensong_kevin | 来源:发表于2019-09-26 11:02 被阅读0次

题目大意:

题目截图

给你一个数,比如12、22、25.....求出该数的阶乘的所有质数因子,并且按照要求的格式返回。

解题思路:

一般人首先想到的就是先求阶乘,然后慢慢除,顺便判断一下是否为素数,然后按要求格式返回。
不说别的,就算你敲出代码肯定也会卡在运行时间上过不去,想想十几的阶乘都很大了,那随便给个千儿八百岂不是jj了,所以要想别的方法。

1、要求的返回格式中有质因子以及该质因子的个数,所以首先定义一个字典存放质因子与其个数。为了避免报出KeyError的错误,我们这样定义:from collections import defaultdict dictionary = defaultdic(lambda:0)。
2、刚刚也提到稍微大点的数的阶乘十分庞大,为了减少运行时间,我们可以将阶乘分开来算,分别计算该数的阶乘中每个数的质数因子。
3、剩下的就不多说,代码简单易读。

代码:

from collections import defaultdict
def dec(n):
    decomp = defaultdict(lambda:0)
    i = 2
    while n > 1:
        while n % i == 0:
            n /= i
            decomp[i] += 1
        i += 1
    return decomp
            
def decomp(n):
    ans = defaultdict(lambda:0)
    for i in range(2, n + 1):
        for key, value in dec(i).items():
            ans[key] += value
    return ' * '.join('{}^{}'.format(x, y) if y > 1 else str(x) for x, y in sorted(ans.items()))

相关文章

网友评论

      本文标题:codewars刷题之 “Factorial decompos

      本文链接:https://www.haomeiwen.com/subject/loiuuctx.html