a[];main(n,i,j,l,m,x,y,z){for(;j=m=i=scanf("%d",&n)>0;)for(bzero(a,999),printf("%d: 1",n);++i<n&&m||printf(++j>n?"\n":m?" %d":" _",m=a[j])>1;m?a[z-~m]=-~i:0)for(a[n-1]=2,m=x=0;x<n-1;l>m&&(z=y,m=l))for(y=x;l=x+++~y>>1,!a[x];);}
Note that non-ascii characters in the above source code will be escaped (such as \x9f).