#Snails, 122 Input should be given in unary. The digits may be any mix of characters except newlines.
^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.
In this 2D pattern matching language, the program state consists solely of the current grid location, the set of cells which have been matched, and the position in the pattern code. It's also illegal to travel onto a matched square. It's tricky, but possible to store and retrieve information. The restriction against traveling onto a matched cell can be overcome by backtracking, teleporting (t) and assertions (=, !) which leave the grid unmodified after completing.
The factorization for an odd composite number begins by marking out some set of mutually non-adjacent cells (blue in diagram). Then, from each yellow cell, the program verifies that there are an equal number of non-blue cells on either side of the adjacent blue one by shuttling back and forth between the two sides. The diagram shows this pattern for one of the four yellow cells which must be checked.
Annotated code:
^ Match only at the first character
..~ | Special case to return true for n=2
!(.2 + ~) Fail for even numbers
. !~ Match 1st character and fail for n=1
!{ If the bracketed pattern matches, it's composite.
(t. l=. r=. =(.,~) )+ Teleport to 1 or more chars and match them (blue in graphic)
Only teleport to ones that have an unmatched char on each side.
The =(.,~) is removed in the golfed code. It forces the
teleports to proceed from left to right, reducing the
time from factorial to exponential.
!{ If bracketed pattern matches, factorization has failed.
t . !. !~ Teleport to a square to the left of a blue square (yellow in diagram)
!{ Bracketed pattern verifies equal number of spaces to
the left or right of a blue square.
{
(r!~ u~)+ Up...
(d!~!. r~)+ Right...
d~, Down...
. r . =. Move 1 to the right, and check that we are not on the edge;
otherwise d~, can fall off next iteration and create and infinite loop
(l!~ u~)+ Up...
(d!~ l~)+ Left...
d ~, Down...
. l . Left 1
} , Repeat 0 or more times
l =(. !.) Check for exactly 1 unused char to the left
(r!~ u~)+ Up...
(d!~!. r~)+ Right...
d ~, Down...
. r . !.
}
}
}