問題一覧 > 通常問題

No.458 Sum of Distinct Primes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 430
作問者 : 小指が強い人 / テスター : 紙ぺーぱー
お気に入りにしたユーザー ProblemId : 931 / 自分の提出
問題文最終更新日: 2026-06-27 14:13:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

Problem Statement

If $N$ can be expressed as a sum of distinct primes, output the maximum number of terms $M$ among such sums.

Input

$N$

$1 \le N \le 20000$ (integer)

Output

$M$
This includes the case where the number can only be expressed by a prime itself.
If it cannot be expressed as a sum of distinct primes, output $-1$.

Sample

Sample 1
Input
18
Output
3

There are "$7+11$" and "$2+5+11$", but "$2+5+11$" has more terms, so the answer is $3$.

Sample 2
Input
4
Output
-1

For $4$ there is "$2+2$", but it is not valid because it contains the same prime more than once.
Since it cannot be expressed as a sum of distinct primes, output $-1$.

Sample 3
Input
3344
Output
41

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。