#! /bin/sed -nf
s/.*/&;9aaaaaaaaa8aaaaaaaa7aaaaaaa6aaaaaa5aaaaa4aaaa3aaa2aa1a0/
:encode
s/\(a*\)\([0-9]\)\([0-9]*;.*\2\(a*\)\)/\1\1\1\1\1\1\1\1\1\1\4\3/
tencode
s/;.*//
# Compute a few common factors for speed. Clear the subst flag
t7a
# These are placed here to make the flow harder to understand :-)
:2
a\
2
b2a
:3
a\
3
b3a
:5
a\
5
b5a
:7
a\
7
:7a
s/^\(aa*\)\1\{6\}$/\1/
t7
:5a
s/^\(aa*\)\1\{4\}$/\1/
t5
:3a
s/^\(aa*\)\1\1$/\1/
t3
:2a
s/^\(aa*\)\1$/\1/
t2
/^a$/b
# The quotient of dividing by 11 is a limit to the remaining prime factors
s/^\(aa*\)\1\{10\}/\1=&/
# Pattern space looks like CANDIDATE\nNUMBER. When a candidate is valid,
# the number is divided and the candidate is tried again
:factor
/^\(a\{7,\}\)=\1\1*$/! {
# Decrement CANDIDATE, and search again if it is still >1
s/^a//
/^aa/b factor
# Print the last remaining factor: since it is stored in the NUMBER
# rather than in the CANDIDATE, swap 'em: now NUMBER=1
s/\(.*\)=\(.*\)/\2=\1/
}
# We have a prime factor in CANDIDATE! Print it
h
s/=.*/;;0a1aa2aaa3aaaa4aaaaa5aaaaaa6aaaaaaa7aaaaaaaa8aaaaaaaaa9/
:decode
s/^\(a*\)\1\{9\}\(a\{0,9\}\)\([0-9]*;.*[^a]\2\([0-9]\)\)/\1\4\3/
/^a/tdecode
s/;.*//p
g
:divide
s/^\(a*\)\(=b*\)\1/\1\2b/
tdivide
y/b/a/
# If NUMBER = 1, we don't have any more factors
/aa$/bfactor