A. Bachgold Problem Codeforces Round #388 (Div. 2)

A. Bachgold Problem

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Bachgold trouble is very convenient to formulate. Given a wonderful integer n signify it as a sum of most feasible range of top numbers. One can show that such illustration exists for any integer larger than 1.

Recall that integer ok is referred to as high if it is larger than 1 and has precisely two superb integer divisors — 1 and k.

Input

The solely line of the enter incorporates a single integer n (2 ≤ n ≤ 100 000).

Output

The first line of the output includes a single integer ok — most viable wide variety of primes in representation.

The 2d line need to comprise okay primes with their sum equal to n. You can print them in any order. If there are a number of top-quality solution, print any of them. 

SOLUTION: 

We want characterize integer range N (1 < N) as a sum of most feasible variety of top numbers, they don’t have to be different.

If N is even number, we can characterize it as sum of solely 2 - minimal top number. It is minimal high number, so range of primes in sum is maximal in this case.

If N is unusual number, we can use representing of N - 1 as sum with solely 2 and change ultimate summand from 2 to 3.

Using of any high P > 3 as summand is no longer optimal, because it can be changed with the aid of extra than one 2 and three 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,i;

    cin>>n;

    cout<<n/2<<endl;

    if (n%2==0){

        for(i=0;i<(n/2)-1;i++)

            cout<<"2 ";

        cout<<"2"<<endl;

        }

    else{

        for(i=0;i<(n/2)-1;i++)

            cout<<"2 ";

        cout<<"3"<<endl;

    }

    return 0;

}