【競技プログラミング】AtCoder Beginner Contest 142_D問題

# 問題
https://atcoder.jp/contests/abc142/tasks/abc142_d

## 要約
1. 正整数A, Bが与えられる。
2. AとBの正の公約数の中からいくつかを選ぶ。
3. 選んだ整数のうち、どの2つの異なる整数も互いに素でなければならない。
4. 上記の条件を満たしながら、最大でいくつの整数を選べるかを求める。


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1

AとBの最大公約数を求め、その最大公約数の素因数分解を行うことで、条件を満たす最大の整数の集合を得ることができる。

## 解法の手順

1. 入力された正整数AとBの最大公約数（GCD）を求める。
2. 得られた最大公約数を素因数分解する。
3. 素因数分解で得られた素因数と1を含む集合を作成する。
4. 集合の要素数を出力する。

## 実装手順

1. ユークリッドの互除法を使用してAとBの最大公約数を計算する。
2. 最大公約数を変数max_divに格納する。
3. 答えを格納するための集合ansを作成し、1を追加する。
4. max_divが1より大きい間、以下の処理を繰り返す：
   a. 2からmax_divの平方根まで順に割り切れる数iを探す。
   b. 割り切れる数iが見つかった場合、max_divをiで割り、iをansに追加する。
   c. 割り切れる数が見つからなかった場合、max_div自体が素数なので、ansに追加し、max_divを1にする。
5. 最後に、ansの要素数（len(ans)）を出力する。


# ACコード1
```python:ac.py
def io_func():
    # 標準入力から2つの整数を受け取る
    return map(int, input().split())

def gcd(a, b):
    # ユークリッドの互除法でGCDを計算
    while b:
        a, b = b, a % b
    return a

def solve(a, b):
    # AとBの最大公約数を計算
    max_div = gcd(a, b)
    
    # 答えを格納するための集合を作成し、1を追加
    ans = set()
    ans.add(1)
    
    # max_divが1より大きい間、素因数分解を行う
    while max_div > 1:
        flg = True
        # 2からmax_divの平方根まで順に割り切れる数を探す
        for i in range(2, int(max_div ** 0.5) + 1):
            if max_div % i == 0:
                max_div //= i
                ans.add(i)
                flg = False
                break
        # 割り切れる数が見つからなかった場合
        if flg:
            ans.add(max_div)
            max_div = 1
    
    # 集合の要素数を出力
    print(len(ans))

# メイン処理
a, b = io_func()
solve(a, b)

###
# a, b: 入力された2つの正整数
# max_div: AとBの最大公約数
# ans: 条件を満たす整数の集合
# flg: 素因数が見つかったかどうかを示すフラグ
# i: 素因数の候補

# 1. io_func関数: 標準入力から2つの整数を受け取る
# 2. gcd関数: ユークリッドの互除法を用いて最大公約数を計算する
# 3. solve関数: 主な処理を行う
#    3.1. AとBの最大公約数を計算
#    3.2. 答えを格納するための集合を作成し、1を追加
#    3.3. 最大公約数が1より大きい間、以下の処理を繰り返す
#         a. 2から最大公約数の平方根まで順に割り切れる数を探す
#         b. 割り切れる数が見つかった場合、その数を集合に追加し、最大公約数を更新
#         c. 割り切れる数が見つからなかった場合、最大公約数自体を集合に追加
#    3.4. 集合の要素数を出力
# 4. メイン処理: io_func関数で入力を受け取り、solve関数を呼び出す

```
## オブジェクト指向版1
```python:ac_object.py
from abc import ABC, abstractmethod
from typing import List, Set

class InputReader(ABC):
    @abstractmethod
    def read_integers(self) -> List[int]:
        pass

class ConsoleInputReader(InputReader):
    def read_integers(self) -> List[int]:
        # 標準入力から2つの整数を受け取る
        return list(map(int, input().split()))

class MathOperations:
    @staticmethod
    def gcd(a: int, b: int) -> int:
        # ユークリッドの互除法でGCDを計算
        while b:
            a, b = b, a % b
        return a

class PrimeFactorizer:
    @staticmethod
    def factorize(n: int) -> Set[int]:
        factors = set()
        factors.add(1)  # 1は常に因数

        # nが1より大きい間、素因数分解を行う
        while n > 1:
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    factors.add(i)
                    n //= i
                    break
            else:
                factors.add(n)
                break

        return factors

class GCDFactorSolver:
    def __init__(self, input_reader: InputReader, math_ops: MathOperations, factorizer: PrimeFactorizer):
        self.input_reader = input_reader
        self.math_ops = math_ops
        self.factorizer = factorizer

    def solve(self) -> int:
        # 入力を読み取る
        a, b = self.input_reader.read_integers()

        # AとBの最大公約数を計算
        max_div = self.math_ops.gcd(a, b)

        # 最大公約数を素因数分解
        factors = self.factorizer.factorize(max_div)

        # 因数の数を返す
        return len(factors)

class ResultPrinter:
    @staticmethod
    def print_result(result: int):
        print(result)

# メイン処理
def main():
    input_reader = ConsoleInputReader()
    math_ops = MathOperations()
    factorizer = PrimeFactorizer()
    solver = GCDFactorSolver(input_reader, math_ops, factorizer)
    result = solver.solve()
    ResultPrinter.print_result(result)

if __name__ == "__main__":
    main()
```

### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
import logging

class PrimeFactorizer:
   def __init__(self):
       self.logger = logging.getLogger(__name__)
       self.logger.setLevel(logging.DEBUG)
       handler = logging.FileHandler('prime_factorizer.log')
       handler.setFormatter(logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s'))
       self.logger.addHandler(handler)

   def factorize(self, n: int) -> Set[int]:
       self.logger.info(f"Starting factorization of {n}")
       factors = set()
       factors.add(1)
       
       while n > 1:
           for i in range(2, int(n ** 0.5) + 1):
               if n % i == 0:
                   factors.add(i)
                   n //= i
                   self.logger.debug(f"Found factor: {i}")
                   break
           else:
               factors.add(n)
               self.logger.debug(f"Found prime factor: {n}")
               break

       self.logger.info(f"Factorization complete. Factors: {factors}")
       return factors
```

#### テスト容易性
```python:ac_object.py
import unittest

class TestPrimeFactorizer(unittest.TestCase):
    def setUp(self):
        self.factorizer = PrimeFactorizer()

    def test_factorize_prime_number(self):
        self.assertEqual(self.factorizer.factorize(17), {1, 17})

    def test_factorize_composite_number(self):
        self.assertEqual(self.factorizer.factorize(12), {1, 2, 3})

    def test_factorize_one(self):
        self.assertEqual(self.factorizer.factorize(1), {1})

    def test_factorize_zero(self):
        self.assertEqual(self.factorizer.factorize(0), {1})

```

#### 可読性と保守性の向上
```python:ac_object.py
   class GCDFactorSolver:
       def __init__(self, input_reader: InputReader, math_ops: MathOperations, factorizer: PrimeFactorizer):
           self.input_reader = input_reader
           self.math_ops = math_ops
           self.factorizer = factorizer

       def solve(self) -> int:
           a, b = self.input_reader.read_integers()
           max_div = self.math_ops.gcd(a, b)
           factors = self.factorizer.factorize(max_div)
           return len(factors)
```

このコードは、入力の読み取り、GCDの計算、素因数分解、結果の計算という一連の処理を明確に示しています。