// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// IntFactorTable.hpp
// 素因数テーブル（エラトステネスの篩で最大素因数を記録）

#ifndef CALX_INT_FACTOR_TABLE_HPP
#define CALX_INT_FACTOR_TABLE_HPP

#include "IntBase.hpp"
#include <vector>
#include <string>

namespace calx {

/**
 * @brief 素因数テーブル（最大素因数版）
 *
 * エラトステネスの篩を用いて、各整数の最大素因数を記録したテーブルを構築します。
 * 最小素因数（SPF）ではなく最大素因数（LPF: Largest Prime Factor）を記録することで、
 * 以下の利点があります：
 *
 * 1. **篩の構築が高速**: 条件分岐なしで無条件に上書きするだけ
 * 2. **素因数分解が高速**: 大きい素数で先に割ることで、桁数が早く減る
 * 3. **コードがシンプル**: 判定処理が不要
 *
 * アルゴリズム:
 *   - 素数 p について、その倍数 m に対して table[m] = p を無条件に上書き
 *   - 小さい素数から大きい素数の順に処理するため、最終的に最大素因数が残る
 *
 * 使用例:
 *   IntFactorTable table(10000);  // 10000 までの素因数テーブルを構築
 *   int lpf = table[360];          // 360 = 2^3 × 3^2 × 5 → lpf = 5
 *   auto factors = table.factorize(Int(360));  // {{2,3}, {3,2}, {5,1}}
 */
class IntFactorTable {
private:
    std::vector<uint32_t> table_;  // 奇数のみ格納（偶数は素因数 2 固定）
    int max_value_;                // テーブルの最大値

public:
    /**
     * @brief コンストラクタ（テーブルを構築）
     *
     * @param max_value テーブルの最大値（デフォルト: 1000000 = 1M）
     *
     * max_value までの素因数テーブルを構築します。
     * テーブル構築には O(n log log n) の時間がかかります。
     *
     * メモリ使用量:
     *   - max_value = 1000:       約 2KB
     *   - max_value = 1000000:    約 2MB
     *   - max_value = 100000000:  約 200MB
     */
    explicit IntFactorTable(int max_value = 1000000);

    /**
     * @brief テーブルの最大値を取得
     */
    int maxValue() const { return max_value_; }

    /**
     * @brief 指定した整数の最大素因数を取得
     *
     * @param n 整数（0 <= n <= max_value）
     * @return 最大素因数（n が素数の場合は 0、n = 0,1 の場合は特殊値）
     *
     * 戻り値:
     *   - n = 0 または n = 1: 0
     *   - n が素数: 0
     *   - n が合成数: 最大素因数
     *   - n が偶数（n > 2）: 2 または最大の奇素因数
     *
     * 注意: n > max_value の場合は 0 を返します（範囲外）
     */
    int operator[](int n) const;

    /**
     * @brief 指定した整数を素因数分解
     *
     * @param n 素因数分解する整数
     * @return 素因数と指数のペアのベクトル {{p1, e1}, {p2, e2}, ...}
     *         p1 < p2 < ... の順（昇順）
     *
     * 例:
     *   factorize(Int(360)) → {{2,3}, {3,2}, {5,1}}  (360 = 2^3 × 3^2 × 5)
     *   factorize(Int(17))  → {{17,1}}  (素数)
     *   factorize(Int(1))   → {}  (空)
     *   factorize(Int(0))   → {{0,1}}  (特殊ケース)
     *
     * 特殊ケース:
     *   - n = 0: {{0, 1}}
     *   - n = 1: {} (空のベクトル)
     *   - n < 0: |n| の素因数分解を返す
     *   - n > max_value: テーブル外の部分は試し割りで分解
     *   - n.isNaN(): {} (空)
     *   - n.isInfinite(): {} (空)
     */
    std::vector<std::pair<Int, int>> factorize(const Int& n) const;

    /**
     * @brief テーブルをファイルに保存
     *
     * @param filename ファイル名（デフォルト: "FactorTable.dat"）
     * @return true: 成功, false: 失敗
     *
     * バイナリ形式で保存:
     *   1. max_value (4 bytes)
     *   2. table のサイズ (4 bytes)
     *   3. table の内容 (uint32_t × size)
     */
    bool saveToFile(const std::string& filename = "FactorTable.dat") const;

    /**
     * @brief テーブルをファイルから読み込み
     *
     * @param filename ファイル名（デフォルト: "FactorTable.dat"）
     * @return true: 成功, false: 失敗
     *
     * ファイルが存在しない、またはサイズが合わない場合は失敗します。
     */
    bool loadFromFile(const std::string& filename = "FactorTable.dat");

private:
    /**
     * @brief エラトステネスの篩でテーブルを構築（最大素因数版）
     *
     * アルゴリズム:
     *   for p = 3 to sqrt(max_value) step 2:
     *       if table[p] == 0:  // p は素数
     *           for m = p^2 to max_value step 2*p:
     *               table[m] = p  // 無条件に上書き（条件判定なし）
     *
     * 最小素因数版との違い:
     *   - SPF: if (table[m] == 0) table[m] = p;  // 条件判定あり
     *   - LPF: table[m] = p;                     // 条件判定なし
     */
    void buildTable();

    /**
     * @brief 奇数のインデックスを内部配列のインデックスに変換
     *
     * @param n 奇数
     * @return 内部配列のインデックス
     *
     * 奇数のみを格納するため、n を 2 で割ったインデックスを使用
     * 例: n=3 → index=1, n=5 → index=2, n=7 → index=3
     */
    size_t oddIndex(int n) const {
        return static_cast<size_t>(n >> 1);
    }
};

} // namespace calx

#endif // CALX_INT_FACTOR_TABLE_HPP