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