2020 BIT冬训-贪心 E - Bachgold Problem CodeForces - 749A

Problem Description

Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k.

Input

The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).

Output

The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.

Examples

Input
5
Output
2
2 3
Input
6
Output
3
2 2 2
其实就三种情况:
n为3的话就是1个3.
n为偶数的话就是n/2个2相加。
n为奇数且不等于三的话就是n/2-1个2和1个3相加。
注意判断偶数时(n&1)==0中的n&1要用括号括起来。
#include<iostream>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%d\n",n/2);
    if(n==3){
        printf("3");
    }else if((n&1)==0){
        for(int i=0;i<n/2;i++)
            printf("2 ");
    }else{
        for(int i=0;i<n/2-1;i++)
            printf("2 ");
        printf("3");
    }
    return 0;
}

 

 



上一篇:数据库|group by查询出其他字段


下一篇:C++ algorithm之any_of