コンテナに金属棒を詰めるのに必要な操作回数を求めるPythonプログラム

異なる長さを持つ複数の金属棒を輸送するタスクが与えられたとしましょう。ところが、輸送用コンテナの長さは短く、長さ1の棒しか収容できません。n 本の棒が与えられ、それぞれの長さはリスト形式で渡されます。すべての棒をコンテナに収めるには、各棒を切断して単位長さ（長さ1）に分割する必要があります。そのうえで、分割したすべての棒をコンテナへ詰め込む作業が1操作としてカウントされます。ここで求めたいのは、棒に対して実行しなければならない操作の合計回数です。

この問題の鍵となるのは素因数分解の活用です。あらかじめエラトステネスの篩（ふるい）で十分な範囲の素数を生成しておくことで、大きな値でも効率的に操作回数を計算できます。

例えば、入力が input_arr = [6, 3, 7] の場合、出力は 22 になります。

• 長さ6の棒を長さ1の棒に分割するには、10回の操作が必要です。

• 長さ3の棒を長さ1の棒に分割するには、4回の操作が必要です。

• 長さ7の棒を長さ1の棒に分割するには、8回の操作が必要です。

アルゴリズムの手順

この問題は、以下の手順に従って解きます。

1. 素数生成関数 prime_find() の定義

引数として input_num を受け取り、その範囲内の素数リストを返します。

• prime_check := サイズが (input_num − 1) // 2 で、すべて True の新しいリストを作成します。

• p_num を 3 から √input_num の切り捨て値 + 1 まで、2 ずつ増やしながら処理します。

  • prime_check[(p_num − 3) // 2] が True の場合、インデックス (p_num² − 3) // 2 以降を p_num 間隔で False に置き換えます（要素数は (input_num − p_num²) // (2 × p_num) + 1）。

• 最後に、True のまま残ったインデックス i から 2 × i + 3 を復元したリストの先頭に 2 を加えたものを返します。

2. メイン処理 solve() の流れ

• prime_nums := prime_find(10⁶ + 100) で素数表を事前生成します。

• result := 0 で初期化します。

• input_arr の各値 value について、以下を繰り返します。

  • まず result に value を加算します。

  • f_list := 空のリストを用意します。

  • prime_nums の各素数 p_num について、value が割り切れる限り p_num を f_list の末尾に追加し、value を p_num で整数除算していきます。

  • p_num² > value となった時点で、value が 1 より大きければその値を f_list に追加し、ループを抜けます。これで value の素因数分解が完成します。

  • temp := 1 とし、f_list を逆順にたどりながら、result に temp を加算し、temp に p_num を掛けて更新します。

• すべての棒を処理し終えた result を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

from math import floor,sqrt

def prime_find(input_num):
    prime_check = [True]*((input_num-1)//2)
    for p_num in range(3,floor(sqrt(input_num))+1,2):
        if prime_check[(p_num-3)//2]: prime_check[(p_num**2-3)//2::p_num] = [False] * ((input_num-p_num**2)//(2*p_num) + 1)
    return [2]+[2*i+3 for i in range((input_num - 1) // 2) if prime_check[i]]

def solve(input_arr):
    prime_nums = prime_find(10**6+100)
    result = 0
    for value in input_arr:
        result += value
        f_list = []
        for p_num in prime_nums:
            while value % p_num == 0:
                f_list.append(p_num)
                value //= p_num
            if p_num**2 > value:
                if value > 1:
                    f_list.append(value)
                break
        temp = 1
        for p_num in f_list[-1::-1]:
            result += temp
            temp *= p_num
    return result

if __name__ == "__main__":
    print(solve([6, 3, 7]))

入力

[6, 3, 7]

出力

22