1#! /bin/sed -nf 2 3s/.*/&;9aaaaaaaaa8aaaaaaaa7aaaaaaa6aaaaaa5aaaaa4aaaa3aaa2aa1a0/ 4:encode 5s/\(a*\)\([0-9]\)\([0-9]*;.*\2\(a*\)\)/\1\1\1\1\1\1\1\1\1\1\4\3/ 6tencode 7s/;.*// 8 9# Compute a few common factors for speed. Clear the subst flag 10t7a 11 12# These are placed here to make the flow harder to understand :-) 13:2 14a\ 152 16b2a 17:3 18a\ 193 20b3a 21:5 22a\ 235 24b5a 25:7 26a\ 277 28 29:7a 30s/^\(aa*\)\1\{6\}$/\1/ 31t7 32:5a 33s/^\(aa*\)\1\{4\}$/\1/ 34t5 35:3a 36s/^\(aa*\)\1\1$/\1/ 37t3 38:2a 39s/^\(aa*\)\1$/\1/ 40t2 41 42/^a$/b 43 44# The quotient of dividing by 11 is a limit to the remaining prime factors 45s/^\(aa*\)\1\{10\}/\1=&/ 46 47# Pattern space looks like CANDIDATE\nNUMBER. When a candidate is valid, 48# the number is divided and the candidate is tried again 49:factor 50/^\(a\{7,\}\)=\1\1*$/! { 51 # Decrement CANDIDATE, and search again if it is still >1 52 s/^a// 53 /^aa/b factor 54 55 # Print the last remaining factor: since it is stored in the NUMBER 56 # rather than in the CANDIDATE, swap 'em: now NUMBER=1 57 s/\(.*\)=\(.*\)/\2=\1/ 58} 59 60# We have a prime factor in CANDIDATE! Print it 61h 62s/=.*/;;0a1aa2aaa3aaaa4aaaaa5aaaaaa6aaaaaaa7aaaaaaaa8aaaaaaaaa9/ 63 64:decode 65s/^\(a*\)\1\{9\}\(a\{0,9\}\)\([0-9]*;.*[^a]\2\([0-9]\)\)/\1\4\3/ 66/^a/tdecode 67s/;.*//p 68 69g 70:divide 71s/^\(a*\)\(=b*\)\1/\1\2b/ 72tdivide 73y/b/a/ 74 75# If NUMBER = 1, we don't have any more factors 76/aa$/bfactor 77