Posts pythonTip 73 分解 n!
Post
Cancel

pythonTip 73 分解 n!

题目描述: 给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式. 质因数分解形式为: n=p1^m1*p2^m2*p3^m3……

  • 这里 p1 < p2 < p3 < …… 为质数

  • 如果 mi = 1, 则 ^ mi 就不需要输出 如:

    n=6, 则输出:6=2^4*3^2*5

    n=7, 则输出:7=2^4*3^2*5*7

示例: 输入: n = 2 输出: 2 = 2

分析:

先统计后输出,输出的时候判断 其指数是否为1。

n 的阶乘的质因数等于 各个 数的质因素和。 例如 n = 6

2 = 2

3 = 2, 3

4 = 2

5 = 5

6 = 2, 3

于是,现在问题就是,如何求一个数的质因数?

这个问题简单撒,就是先得到所有不大于当前数的质数,然后依次判断一下是否是当前数的因数就可以了。

然后问题就变成了,如何得到所有的质数呢? 就是依次和小于当前数的所有质数做判断,判断是否构成倍数关系,如果一个数不是小于它的所有质数的倍数,那么这个数就是一个素数。所以基于这一点,我一边生成质数数组,一边求质因数。详情见代码。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ans = []

res = {}

for value in range(2, n+1):
    flag = False
    for it in ans:
        while not value % it:
            num = res.get(it)
            res[it] = num + 1
            value /= it
            flag = True
    if not flag:
        ans.append(value)
        res[value] = 1

print("{}=".format(int(n)), end="")

r = []
for a in ans:
    if res[a] == 1:
        r.append("{}".format(str(a)))
    else:
        r.append("{}^{}".format(str(a), str(res[a])))

print("*".join(r))
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 72 球迷购票问题

pythonTip 74 C(n,k)

Trending Tags