1 #! /bin/sed -nf 2 3 s/.*/&;9aaaaaaaaa8aaaaaaaa7aaaaaaa6aaaaaa5aaaaa4aaaa3aaa2aa1a0/ 4 :encode 5 s/\(a*\)\([0-9]\)\([0-9]*;.*\2\(a*\)\)/\1\1\1\1\1\1\1\1\1\1\4\3/ 6 tencode 7 s/;.*// 8 9 # Compute a few common factors for speed. Clear the subst flag 10 t7a 11 12 # These are placed here to make the flow harder to understand :-) 13 :2 14 a\ 15 2 16 b2a 17 :3 18 a\ 19 3 20 b3a 21 :5 22 a\ 23 5 24 b5a 25 :7 26 a\ 27 7 28 29 :7a 30 s/^\(aa*\)\1\{6\}$/\1/ 31 t7 32 :5a 33 s/^\(aa*\)\1\{4\}$/\1/ 34 t5 35 :3a 36 s/^\(aa*\)\1\1$/\1/ 37 t3 38 :2a 39 s/^\(aa*\)\1$/\1/ 40 t2 41 42 /^a$/b 43 44 # The quotient of dividing by 11 is a limit to the remaining prime factors 45 s/^\(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 61 h 62 s/=.*/;;0a1aa2aaa3aaaa4aaaaa5aaaaaa6aaaaaaa7aaaaaaaa8aaaaaaaaa9/ 63 64 :decode 65 s/^\(a*\)\1\{9\}\(a\{0,9\}\)\([0-9]*;.*[^a]\2\([0-9]\)\)/\1\4\3/ 66 /^a/tdecode 67 s/;.*//p 68 69 g 70 :divide 71 s/^\(a*\)\(=b*\)\1/\1\2b/ 72 tdivide 73 y/b/a/ 74 75 # If NUMBER = 1, we don't have any more factors 76 /aa$/bfactor 77
