結果

問題 No.458 異なる素数の和
ユーザー atommy-euph
提出日時 2025-02-17 17:58:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
MLE  
実行時間 -
コード長 1,207 bytes
コンパイル時間 580 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 527,120 KB
最終ジャッジ日時 2025-02-17 17:58:48
合計ジャッジ時間 4,102 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def max_prime_partition(N):
    from functools import lru_cache

    # エラトステネスの篩で素数列挙
    def sieve(limit):
        is_prime = [True] * (limit + 1)
        is_prime[0] = is_prime[1] = False
        primes = []
        for i in range(2, limit + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, limit + 1, i):
                    is_prime[j] = False
        return primes

    primes = sieve(N)
    P = len(primes)
    import sys
    sys.setrecursionlimit(10101010)
    # メモ化再帰 DFS (残りの値 `remain` を `i` 以降の素数で作る)
    @lru_cache(None)
    def dfs(remain, i):
        if remain == 0:
            return 0  # 何も足さないときのカウントは0
        if remain < 0 or i >= P:
            return -float("inf")  # 不可能な場合

        # 使わない場合
        res = dfs(remain, i + 1)

        # 使う場合（異なる素数のみ）
        if primes[i] <= remain:
            res = max(res, 1 + dfs(remain - primes[i], i + 1))

        return res

    ans = dfs(N, 0)
    return ans if ans > 0 else -1

# テストケース
N = int(input())
print(max_prime_partition(N))
0