競プロ記録

問題を解いた際に自分の復習用として使ってます

yukicoder No.458

解説

基本的な解答の方針は動的計画法です。

小さい素数から順番に見ていって、i番目までの素数で構成される数に対してi+1番目の新たな素数を加えれば、その和の数は異なる素数で表すことができることになります。 そこで素数を加えた回数を保持するために、i番目までの素数で構成される数の個数に1を加えたもの(i+1番目の素数を加えるので)と元の値とを比較すれば素数の数の最大値を保持できるようになります。

ここで i+1番目の素数にi番目までの素数で構成される数を加えるのですが、n以下で小さい方から加えていってしまうと、同じ素数を複数回加えることになってしまいます。 例えば素数は 2, 3, 5, 7, …. ですが 3(i番目までの素数で構成される数)に対して5を加えると8となり, 5は個数2(2+3)であり、8の個数は3になります。そして8の個数は3となり、再び5を加えることになるため、同じ素数を複数回カウントしてしまい適切ではありません。

しかしn以下で大きい方から加えていくと次加える数より必ず大きくなるので同じ素数を複数回加えることはありません。

コード

#include <iostream>
using namespace std;

int prime[20001];
bool is_prime[20001];
int p = 0;
void eratos(int n){
    for(int i=0; i<=n; i++){
        is_prime[i] = true;
    }
    is_prime[0] = is_prime[1] = false;
    for(int i=2; i<=n; i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= n; j += i){
                is_prime[j] = false;
            }
        }
    }
}

int main(void){
    int n;
    cin >> n;
    eratos(20000);
    int dp[20000];
    fill(dp, dp+20000, -1);
    dp[0] = 0;
    for(int i=0; i<p; i++){
        for(int j=n; j >= 0; j--){
            if(dp[j] != -1 && prime[i] + j <= n){
                dp[prime[i]+j] = max(dp[prime[i]+j], dp[j]+1);
            }
        }
    }
    cout << dp[n] << endl;

    return 0;
}