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
Input5Output
2Input
2 3
6Output
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; }