リスト内の要素を使って合計値を60にしたい

問題１　足し算するとちょうど60になる素数の組み合わせを出力するプログラムを作成せよ。
問題２　足し算するとちょうど60になるような10個以上の素数の組み合わせを出力するプログラムを作成せよ。
上記２問とも重複ありです。(例41,3,2,2,2,2,2,2,2,2など)
私は先に60までの素数をリストに格納して、それらを使って合計60になるような組み合わせを探そうとしました。しかし、私の作ったプログラムはとてつもない計算量になってしまい、実行できません。そもそもの考え方が間違っているのか、もっと効率よくリスト内の値を計算する方法があるのか分かる方教えて下さい。

python
1limit = 60
2list = []
3list_1 = []
4for i in range(2, limit):
5    for j in range(2, i):
6        if i % j == 0:
7            break
8    else:
9        list.append(i)
10for k in(list):
11    a = int(60/k)
12    for l in range(a):
13        list_1.append(k)
14
15def get_integral_value_combination(list, target):
16    def a(idx, l, r, t):
17        if t == sum(l): r.append(l)
18        elif t < sum(l): return
19        for u in range(idx, len(list)):
20            a((u + 1), l + [list[u]], r, t)
21        return r
22    return a(0, [], [], target)
23
24print(get_integral_value_combination(list_1, 60))

行動規範の内容に同意します

回答1件

ベストアンサー

素数を重複登録して、通常の部分和問題の解法を使っているのが、一番の問題だと思います。
重複登録した数値それぞれが別物として扱われて、同じ組み合わせが複数回カウントされます。
例えば、ご提示のコードで、和を60ではなく7にして実行すると、2種類の解が合計9回現れます。

また、sum(l)を何度も使っているのも時間がかかる原因です。
これだと、lの長さに比例する時間が毎回かかってしまいます。
lに追加した数字の分だけtを減らせばよいのだから、毎回合計を計算する必要はありません。

とりあえず、最初の問題だけ解決すれば、動作するようにはなります。(他にいろいろ問題が残っていますが)

python
1limit = 60
2list = []
3for i in range(2, limit):
4    for j in range(2, i):
5        if i % j == 0:
6            break
7    else:
8        list.append(i)
9
10def get_integral_value_combination(list, target):
11    def a(idx, l, r, t):
12        if t == sum(l): r.append(l)
13        elif t < sum(l): return
14        for u in range(idx, len(list)):
15            a(u, l + [list[u]], r, t)
16        return r
17    return a(0, [], [], target)
18
19print(get_integral_value_combination(list, 60))