LoginSignup
1
2

More than 3 years have passed since last update.

【Python 3】14行で素因数分解

Last updated at Posted at 2020-05-21

意外とPythonの標準ライブラリに素因数分解ってないんですね。
Counterを使ってシンプルに書いてみました。上から14行で。

prime_factorization.py
from math import sqrt
from collections import Counter

def prime_factorization(n):
    counter = Counter()
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            counter[i] += 1

    if n != 1:
        counter[n] += 1

    return list(counter.items())

def prime_factors(n):
    return set(map(lambda x: x[0], prime_factorization(n)))

if __name__ == '__main__':
    # 2020 = 2^2 * 5^1 * 101^1
    print(prime_factorization(2020)) # => [(2, 2), (5, 1), (101, 1)]
    print(prime_factors(2020)) # => {2, 101, 5}
    # 1の場合はからのリストを返す
    print(prime_factorization(1)) # => []

参考

Pythonで高速素因数分解〜競プロ用〜

1
2
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2