問題
既存投稿一覧ページへのリンク
解法手順1
解法アプローチ
- 素数のリストを生成する。
- 二重ループを使用して、条件を満たす組み合わせを探索する。
- 探索範囲を最適化し、計算量を削減する。
- 条件を満たす組み合わせの数をカウントする。
具体的手順
- 入力値Nを受け取る。
- 素数のリストを生成する：
- 2から(10^18)^(1/3)+2までの数を調べる。
- エラトステネスの篩の考え方を用いて素数を判定する。
- 素数をリストに追加する。
- 結果を格納する変数resultを0で初期化する。
- 素数リストの要素を順に走査する：
- 現在の素数をlとする。
- lがN^(1/3)より大きくなったら探索を終了する。
- lより大きい素数rについて探索する：
- l*(r^3)がNを超えたら、その手前の素数まで戻る。
- l*(r^3)がN以下の場合：
- 条件を満たす組み合わせの数を結果に加算する。
- 全ての探索が終わったら、resultを出力する。
ACコード1
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
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()
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
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())
テスト容易性
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) # 期待される結果