#include <stdio.h>#include <stdlib.h>#include <string.h>#define OO 10001bool used[ 10001 ];int prime[ 1231 ];int madelist(){ memset( used, 0, sizeof( used ) ); int count = 0; for ( int i = 2 ; i < 10000 ; ++ i ) if ( !used[ i ] ) { prime[ ++ count ] = i; for ( int j = i<<1 ; j < 10000 ; j += i ) used[ j ] = 1; } return count;}int f[ 10001 ];int t[ 10001 ];int main(){ int C = madelist(); for ( int i = 0 ; i <= 10000 ; ++ i ) { f[ i ] = OO; t[ i ] = 0; } f[ 0 ] = 0; for ( int i = 1 ; i <= C ; ++ i ) for ( int j = prime[ i ] ; j <= 10000 ; ++ j ) if ( f[ j ] > f[ j-prime[ i ] ]+1 ) { f[ j ] = f[ j-prime[ i ] ]+1; t[ j ] = prime[ i ]; } int n; while ( ~scanf("%d",&n) ) { if ( t[ n ] ) { printf("%dn%d",f[ n ],t[ n ]); int v = n-t[ n ]; while ( t[ v ] ) { printf(" %d",t[ v ]); v = v-t[ v ]; } }else printf("0"); printf("n"); } return 0;}
