Codeforces Round #324 (Div. 2) D. Dima and Lisa

問題

codeforces.com

解法

本番は「素数　和　奇数」で検索したらいい感じの結果が出たのでそれを参考にしてやりました。

多分「弱いゴールドバッハの予想」というのが出てくると思います。さらに下の方まで読んでいくと「5より大きい奇数は 1 個の奇素数と 2 個の同じ素数の和で表せる」という予想（Lemoine予想）と書いてあるものがあり, これを今回は採用しました。
要するに, n を奇数として n = p + 2q 　　（p, q は素数） となるということです。

また, 理由は知りませんが, 一般に整数 n が素数になる確率は 1/log(n) に収束するという定理(ちょっと適当に書いてます)があるので, 今回の場合は p を n に近い順に調べて行って 上手いこと q が素数になるようなものを探せばなんとなく時間内に解けそうな気がします。

下のコードでは念の為別の場合もちょくちょく書いてます(必須なのもあります)。

bool prime(ll n) {
    for (int i = 2; i*i <= n; i++) if (n%i == 0) return false;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    if (prime(n)) {
        cout << 1 << endl;
        cout << n << endl;
        return 0;
    }
    if (prime(n-2)) {
        cout << 2 << endl;
        cout <<  2 << " " << n-2 << endl;
        return 0;
    }
    for (ll i = n-4; ; i -= 2) {
        if (prime(i)) {
            ll rest = (n-i) / 2;
            if (prime(rest)) {
                cout << 3 << endl;
                cout << rest << " " << rest << " " << i << endl;
                return 0;
            }
        }
    }
    return 0;
}