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

# 問題
https://atcoder.jp/contests/abc250/tasks/abc250_d

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

# 解法手順1

## 解法アプローチ

1. 素数のリストを生成する。
2. 二重ループを使用して、条件を満たす組み合わせを探索する。
3. 探索範囲を最適化し、計算量を削減する。
4. 条件を満たす組み合わせの数をカウントする。

## 具体的手順

1. 入力値Nを受け取る。
2. 素数のリストを生成する：
   - 2から(10^18)^(1/3)+2までの数を調べる。
   - エラトステネスの篩の考え方を用いて素数を判定する。
   - 素数をリストに追加する。
3. 結果を格納する変数resultを0で初期化する。
4. 素数リストの要素を順に走査する：
   - 現在の素数をlとする。
   - lがN^(1/3)より大きくなったら探索を終了する。
5. lより大きい素数rについて探索する：
   - l*(r^3)がNを超えたら、その手前の素数まで戻る。
6. l*(r^3)がN以下の場合：
   - 条件を満たす組み合わせの数を結果に加算する。
7. 全ての探索が終わったら、resultを出力する。


# ACコード1
```python:ac.py
import math

def io_func():
    # 入力値Nを受け取る
    n = int(input())
    return n

def generate_primes(limit):
    # 素数のリストを生成する関数
    primes = []
    for i in range(2, limit):
        is_prime = True
        for prime in primes:
            if prime > math.sqrt(i):
                break
            if i % prime == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    return primes

def solve(n):
    # 素数のリストを生成する
    primes = generate_primes(int((10**18)**(1/3)) + 2)
    
    # 結果を格納する変数resultを0で初期化する
    result = 0
    
    # 素数リストの要素を順に走査する
    for i in range(len(primes)):
        l = primes[i]
        
        # lがN^(1/3)より大きくなったら探索を終了する
        if l > n**(1/3):
            break
        
        # lより大きい素数rについて探索する
        for j in range(i+1, len(primes)):
            r = primes[j]
            # l*(r^3)がNを超えたら、その手前の素数まで戻る
            if l * (r**3) > n:
                j -= 1
                r = primes[j-1]
                break
        
        # l*(r^3)がN以下の場合、条件を満たす組み合わせの数を結果に加算する
        if l * (r**3) <= n:
            result += j - i
    
    # 結果を出力する
    print(result)

# メイン処理
n = io_func()
solve(n)

###
# - n: 入力値N
# - primes: 生成された素数のリスト
# - result: 条件を満たす組み合わせの数
# - l: 現在の素数（ループの外側）
# - r: 現在の素数（ループの内側）
# - i, j: ループのインデックス

# 1. io_func関数:
#    - 標準入力から整数Nを読み込む
# 2. generate_primes関数:
#    - 与えられた上限までの素数を生成する
#    - エラトステネスの篩の考え方を用いて効率的に素数を判定する
# 3. solve関数:
#    - generate_primes関数を呼び出して素数のリストを生成する
#    - 二重ループを使用して条件を満たす組み合わせを探索する
#    - 探索範囲を最適化し、計算量を削減する
#    - 条件を満たす組み合わせの数をカウントする
#    - 結果を出力する
# 4. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く

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

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        # 標準入力から整数Nを読み込む
        return int(input())

class PrimeGenerator:
    def generate_primes(self, limit):
        # 素数のリストを生成する
        primes = []
        for i in range(2, limit):
            is_prime = True
            for prime in primes:
                if prime > math.sqrt(i):
                    break
                if i % prime == 0:
                    is_prime = False
                    break
            if is_prime:
                primes.append(i)
        return primes

class ProblemSolver:
    def __init__(self, prime_generator, logger):
        self.prime_generator = prime_generator
        self.logger = logger

    def solve(self, n):
        # 素数のリストを生成する
        primes = self.prime_generator.generate_primes(int((10**18)**(1/3)) + 2)
        self.logger.debug(f"素数リストを生成しました。長さ: {len(primes)}")
        
        # 結果を格納する変数resultを0で初期化する
        result = 0
        
        # 素数リストの要素を順に走査する
        for i in range(len(primes)):
            l = primes[i]
            self.logger.debug(f"現在の素数 l: {l}")
            
            # lがN^(1/3)より大きくなったら探索を終了する
            if l > n**(1/3):
                self.logger.debug(f"{l} > N^(1/3)のため探索を終了します")
                break
            
            # lより大きい素数rについて探索する
            self.logger.debug(f"lより大きい素数rについて探索する")
            for j in range(i+1, len(primes)):
                r = primes[j]
                # l*(r^3)がNを超えたら、その手前の素数まで戻る
                if l * (r**3) > n:
                    self.logger.debug(f"{l}*({r}^3)がNを超えたら、その手前の素数まで戻る")
                    j -= 1
                    r = primes[j-1]
                    self.logger.debug(f"l*r^3 > N のため、r を {r} に戻します")
                    break
            
            # l*(r^3)がN以下の場合、条件を満たす組み合わせの数を結果に加算する
            if l * (r**3) <= n:
                self.logger.debug(f"{l}*({r}^3)がN以下の場合、条件を満たす組み合わせの数を結果に加算する")
                result += j - i
                self.logger.debug(f"条件を満たす組み合わせを j={j} - i={i} = {j - i} 個見つけました")
        
        self.logger.info(f"計算結果: {result}")
        return result

class OutputWriter:
    def write_output(self, result):
        # 結果を出力する
        print(result)

class ProblemSolverApp:
    def __init__(self, input_reader, problem_solver, output_writer):
        self.input_reader = input_reader
        self.problem_solver = problem_solver
        self.output_writer = output_writer

    def run(self):
        # 入力を読み込む
        n = self.input_reader.read_input()
        # 問題を解く
        result = self.problem_solver.solve(n)
        # 結果を出力する
        self.output_writer.write_output(result)

if __name__ == "__main__":
    debug_mode = True  # デバッグモードを有効にする場合はTrueに設定
    logger = setup_logger(debug_mode)
    
    input_reader = ConsoleInputReader()
    prime_generator = PrimeGenerator()
    problem_solver = ProblemSolver(prime_generator, logger)
    output_writer = OutputWriter()
    
    app = ProblemSolverApp(input_reader, problem_solver, output_writer)
    app.run()

```
### オブジェクト図

![sequence_diagram.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/e7b0bbde-1eb1-a7b4-cdec-21da72bad0a4.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputReader(InputReader):
   def __init__(self, filename):
       self.filename = filename

   def read_input(self):
       with open(self.filename, 'r') as file:
           return int(file.read().strip())
```

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

class TestProblemSolver(unittest.TestCase):
    def setUp(self):
        self.prime_generator = PrimeGenerator()
        self.logger = setup_logger(True)
        self.problem_solver = ProblemSolver(self.prime_generator, self.logger)

    def test_solve(self):
        # テスト実行
        result = self.problem_solver.solve(1000)
        self.assertEqual(result, 4)  # 期待される結果
```