結果

問題 No.458 異なる素数の和
ユーザー Rin Kawamata
提出日時 2025-04-29 10:55:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 877 bytes
コンパイル時間 2,459 ms
コンパイル使用メモリ 197,528 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-29 10:55:05
合計ジャッジ時間 4,026 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
vector<bool> Eratosthenes(int n){
    vector<bool> isPrime(n+1,true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int p = 2; p*p <= n; p++){
        if(isPrime[p]){
            for(int q = p*2; q <= n; q+=p){
                isPrime[q] = false;
            }
        }
    }
    return isPrime;
}
int main(){
    int n;
    cin >> n;
    vector<bool> isPrime = Eratosthenes(n);
    vector<int> Prime;
    vector<int> dp(n+1,-1);//合計がiになるときの和の回数の最大値
    for(int i = 0; i <= n; i++){
        if(isPrime[i]){
            Prime.push_back(i);
        }
    }
    dp[0] = 0;
    for(auto p : Prime){
        for(int i = n; i >= 0; i--){
            if(p+i <= n && dp[i] != -1){
                dp[p+i] = max(dp[p+i],dp[i] + 1);
            }
        }
    }
    cout << dp[n] << endl;
    
}
0