Python - 素因数分解!

Updated:


Python 3 で任意の自然数を素因数分解する方法についての記録です。(あまりに簡単なアルゴリズムですが)

0. 前提条件

  • LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
  • Python 3.6.4 での作業を想定。
  • 当方は他のバージョンとの共存環境であり、 python3.6, pip3.6 で 3.6 系を使用するようにしている。(適宜、置き換えて考えること)

1. アルゴリズムについて

当ブログ過去記事を参照。

2. Python スクリプトの作成

  • 敢えてオブジェクト指向で作成している。
  • Shebang ストリング(1行目)では、フルパスでコマンド指定している。(当方の慣習

File: prime_fractorization.py

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
27
28
29
30
31
32
33
34
35
#! /usr/local/bin/python3.6
"""
Prime fractorization
"""
import sys
import traceback


class PrimeFractorization:
    def __init__(self):
        self.a = 2

    def decomposit_prime(self, n):
        try:
            while n >= self.a * self.a:
                if n % self.a == 0:
                    print(self.a, "* ", end="")
                    n //= self.a
                else:
                    self.a += 1
            print(n)
        except Exception as e:
            raise


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("USAGE: ./prime_factorization.py N")
        sys.exit(0)
    try:
        obj = PrimeFractorization()
        obj.decomposit_prime(int(sys.argv[1]))
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)

3. Python スクリプトの実行

まず、実行権限を付与。

$ chmod +x prime_fractorization.py

そして、第1引数に自然数を指定して実行。

$ ./prime_fractorization.py 100
2 * 2 * 5 * 5

$ ./prime_fractorization.py 1122332211
3 * 3 * 7 * 7 * 11 * 13 * 13 * 37 * 37

以上





 

Sponsored Link

 

Comments