pythonで素因数分解したものを指数表現で表したい

pythonで素因数分解したものを指数表現で表したいです。
2^43^35のように表したいです。
どこを変えればいいかわからずわかる方がいましたら教えてください。

python
1def prime(n):
2    a = []
3    while n % 2 == 0:
4        a.append(2)
5        n //= 2
6    f = 3
7    while f * f <= n:
8        if n % f == 0:
9            a.append(f)
10            n //= f
11        else:
12            f += 2
13    if n != 1:
14        a.append(n)
15    return a
16
17
18print("入力された数の素因数分解を求めます")
19n = int(input())
20print(prime(n))

LouiS0616

2020/04/03 08:15

素因数云々の話は一旦忘れて、例えば [2, 2, 2, 3, 3, 5] から "2^3*3^2*5" を生成する処理を考えて下さい。これらは独立した問題として考えた方が良いでしょう。

行動規範の内容に同意します

回答2件

ベストアンサー

関数の返り値が [2, 2, 2, 3, 5] のような形なので、collections.Contour で2が3個、3が1個、5が1個というように各数が何個あるか数えて、その情報から文字列表記を作成すればよいです。

python
1from collections import Counter
2
3def prime(n):
4    a = []
5    while n % 2 == 0:
6        a.append(2)
7        n //= 2
8    f = 3
9    while f * f <= n:
10        if n % f == 0:
11            a.append(f)
12            n //= f
13        else:
14            f += 2
15    if n != 1:
16        a.append(n)
17    return a
18
19print("入力された数の素因数分解を求めます")
20n = int(input())
21ret = prime(n)
22print(ret)  # [2, 2, 2, 3, 5]
23
24cnt = Counter(ret)
25ret_str = " * ".join(f"{k}^{v}" for k, v in cnt.items())
26print(f"{n} = {ret_str}")  # 2^3 * 3^1 * 5^1

投稿2020/04/03 08:18

編集2020/04/03 08:19

tiitoi

総合スコア21956

pp.py

python3
1def factorize(n):
2    fct = []  # prime factor
3    b, e = 2, 0  # base, exponent
4    while b * b <= n:
5        while n % b == 0:
6            n = n // b
7            e = e + 1
8        if e > 0:
9            fct.append((b, e))
10        b, e = b + 1, 0
11    if n > 1:
12        fct.append((n, 1))
13    return fct
14
15
16TESTS = [1, 2, 3, 60, 120, 360, 1000, 
17    2**3 * 3**4 * 5**5 * 7**6 * 11**7 * 13 ** 8]
18for n in TESTS:
19    facts = factorize(n)
20    exp = " * ".join("{}^{}".format(p, e) for p, e in facts)
21    print("{} = {}".format(n, exp))