PrimesSum

/* 
   Bài tập: Kiểm tra xem số n<10^9 có phân tích được tổng của các số nguyên tố khác nhau không?
            Nếu có ghi ra cách phân tích gồm các số hạng nguyên tố ở đầu nhỏ nhất có thế.
            Nếu không có in ra "invalid".
   CODE BY antovip123@gmail.com
*/
#include<bits/stdc++.h>
std::vector<int> a;
void primeArr(int n, std::vector<int> &a) {
    std::vector<bool> v(n);
    for(int i=1; i<n; i++) {
        v[i] = true;
    }
    for(int i=2; i<=n; i++)
    if(v[i]) {
        for(int j=2; j<=n/i; j++)
            v[i*j] = false;
    }
    for(int i=2; i<=n; i++)
        if(v[i])
            a.push_back(i);
}
bool primeCheck(int n) {
    if(n<2) return false;
    for(int i=2; i<=sqrt(n); i++)
        if(n%i == 0)
        return false;
    return true;
}
bool check(int n, int i) {
    //std::cout<<a[i]<<' ';
    if(n<2) return false;
    if(primeCheck(n) && (n>a[i] || i == -1)) {
        if(i != -1) std::cout<<n<<'+';
        return true;
    }
    for(int j = i+1; j<a.size(); j++)
        if(check(n-a[j], j)) {
            std::cout<<a[j];
            if(j>0) std::cout<<'+';
            else std::cout<<'\n';
            return true;
        }
    //std::cout<<'\n';
    return false;
}
int main() {
    int k = 100000;
    primeArr(k, a);
//    for(int i=0; i<a.size(); i++)
//        std::cout<<a[i]<<' ';
    int n;
    std::cin>>n;
    if(!check(n, -1)) std::cout<<"invalid";
    else std::cout<<"valid";
    return 0;
}