题解

内存击败100%用户
时间击败100%用户

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int num) { // 最完整的isprime模板！
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

vector<int> f(int x, int y) {
    vector<int> primes;
    for (int num = x; num <= y; ++num) {
        if (is_prime(num)) {
            primes.publicsh_back(num);
        }
    }
    return primes;
}

int pack(const vector<int>& primes, int capacity) {
    vector<int> dp(capacity + 1, 0);
    for (int prime : primes) {
        for (int w = capacity; w >= prime; --w) {
            dp[w] = max(dp[w], dp[w - prime] + prime);
        }
    }
    return dp[capacity];
}

int main() {
    int x, y, m;
    cin >> x >> y >> m;

    vector<int> primes = f(x, y);
    int res = pack(primes, m);
    cout << res << endl;

    return 0;
}