Codeforces #325 Div. 2 D Dima and Lisa

2015/10/07 (Wed) Codeforces 数学 探索

問題

問題文

方針

正の整数を適当に選んだときそれが素数である確率はかなり高い．なので本当に適当に探索すると通ってしまう．

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(ll i=(a);i<ll(b);i++)
#define rep(i,b) loop(i,0,b)

int rand(int l, int r){
    int d = r - l + 1;
    return rand()%d + l;
}

vector<int> EratosthenesSieve(int n){
    vector<int> ps(n+1);
    loop(i,2,n+1) ps[i] = i;
    for (int i = 2; i*i <= n; ++i)
        if (ps[i])
            for (int j = i*i; j <= n; j+=i)
                ps[j] = 0;
    ps.erase(remove(ps.begin(), ps.end(), 0), ps.end());
    return ps;
}
const auto ps = EratosthenesSieve(1e5);

bool isPrime(int n){
    if(n <= 1) return false;
    for(auto & p : ps){
        if(p*p > n) break;
        if(n%p==0) return false;;
    }
    return true;
}

// 2つ
vector<int> solve2(int n){
    for(auto & p : ps){
        if(p > n) break;
        if(isPrime(n-p)) return {p, n-p};
    }
    return {};
}

vector<int> solve(int n){
    // 1つ
    if(isPrime(n)) return {n};
    // 2は厄介
    if(n > 4){
        if(isPrime(n-4)) return { 2,2,n-4 };
    }
    if(n > 2){
        if(isPrime(n-2)) return { 2,n-2 };
    }
    // 2つ以上
    for(auto & p : ps){
        if(p > n) break;
        if(isPrime(n-p)) return { p,n-p };
        // 3つ
        auto ans = solve2(n-p);
        if(ans.size()){
            ans.push_back(p);
            return ans;
        }
    }
    return {};
}

signed main(){
    int n;
    while(cin >> n){
        auto ans = solve(n);
        cout << ans.size() << endl;
        for(auto & e : ans) cout << e << " ";
        cout << endl;
    }
}