Semiprime factorization is as easy as 123 by tails

char a[200],b[200],c[200];l;

p(a,b,c,d){
  for(d=l;d--;){
    c=d[a?:""];
    c&&putchar(c+48);
  }
  printf(b);
}

z(d,e,f,g,h){
  if(d<l){
    for(f=1;f<d;++f){
      e+=a[f]*b[d-f];
    }
    for(f=0;f<(d&&!a[d-1]?:4);++f){
      for(g=!!f;g<(d&&!b[d-1]?:4);++g){
        h=d?e+f**b+g**a:f*g;
        if(h%10==c[l+~d]-48){
          a[d]=f;
          b[d]=g;
          z(d+1,h/10);
        }
      }
    }
  }else{
    e||p(a," * ")+p(b,"\n");
  }
}

main(){
  while(gets(c)){
    l=strlen(c);
    z(0,0);
  }
}

Note that non-ascii characters in the above source code will be escaped (such as \x9f).

download

return to the top page