t(n) = { my (d=digits(n), m=0, ii, jj); for (i=1, #d, if (d[i], for (j=i, #d, my (x=fromdigits(d[i..j])); if (m<x && isprime(x), m=x; ii=i; jj=j ); ); ); ); if (m, return (fromdigits(concat([d[1..ii-1], digits(primepi(m)), d[jj+1..#d]]))), return (n) ); } a(n) = while (n!=n=t(n), ); n for (n=0, 100 000, print (n " " a(n))) quit