結果
| 問題 | No.458 異なる素数の和 |
| ユーザー |
 Yuu Eguci
|
| 提出日時 | 2020-11-30 18:05:34 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,478 bytes |
| コンパイル時間 | 159 ms |
| コンパイル使用メモリ | 10,948 KB |
| 実行使用メモリ | 17,228 KB |
| 最終ジャッジ日時 | 2023-10-11 02:57:29 |
| 合計ジャッジ時間 | 6,754 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
ソースコード
"""
N をそれぞれ異なる素数の和で表すことができる場合，その中での最大の和の回数 M を出力してください。
素数自身でしか表せない場合も含みます。
異なる素数の和で表すことができない場合は -1 を出力してください。
"""
from math import sqrt
from itertools import combinations
def foo(N: int):
# 2〜N の中の素数を列挙します。
primes_in_N = get_primes_until_n(N)
# 回答アイデア1……
M = bar(primes_in_N, N)
return M
def bar(primes_in_N, N):
"""回答パターン1"""
# 「は〜い i 人一組になって〜!」
# 素数グループの中から、小さなグループを作っていきます。
# グループの人数は、マックスからだんだん減らしていきます。
for i in range(len(primes_in_N), 0, -1):
# itertools.combinations は全組み合わせを作ってくれます。
# N が大きくなるととんでもないパターン数になる箇所。
for j, combination in enumerate(combinations(primes_in_N, i)):
# 足して N になったらそれが答えです。
if sum(combination) == N:
return len(combination)
return -1
def get_primes_until_n(N: int):
"""N までの素数一覧を返します。"""
# 2〜N の dictionary です。
# この先の処理で、素数でないものは False にしていきます。最終的に値が True のまま残った key が素数です。
# NOTE: list にして、 index を key 扱いしたほうがイカすんだけど dictionary のほうがわかりやすいかと思って。
dic = {i: True for i in range(2, N + 1)}
# N の平方根までチェックすれば、全部の数の素数判定は終わります。
for i in range(2, int(sqrt(N)) + 1):
# すでに False(素数ではない)判定になっているものは計算不要です。
if dic[i] is False:
continue
# 2 から始まるので、その先の倍数を全部 False(素数ではない)にしていけば最後には素数だけが True で残ります。
j = i * 2
while j <= N:
dic[j] = False
j += i
return [i for i in dic.keys() if dic[i]]
# print(foo(18) == 3)
# print(foo(4) == -1)
# print(foo(3) == 1)
# print(foo(1) == -1)
# print(foo(3344) == 41)
# 提出用
print(foo(int(input())))