With input numbers up to 65,535 and a limit of 100,000 steps we have to be at least a bit smart about our algorithm. We will implement the almost-naive O(sqrt(N)) algorithm: Try all b between 2 and sqrt(N), and for each such b try dividing the current N. At the end either N=1 and we are done, or N is one large prime, we print it and we are done.
The actual code follows and is explained below.
>a 1 >o 2 >b :loop Eaoend <a <b % >c Zcdiv <b 1 + >b :check <a <b / >d Gbdlast Jloop :div <a <b / >a <b P Jloop :last Eaoend <a P :end
We store the input number in the register a, and initialize registers o to 1
and b to 2.
In the :loop loop we check whether a mod b is zero. If no, we increase
b and in the :check part check whether we already passed sqrt(a).
If a was divisible by b, we divide it, print b, and without increasing b jump back to the start of the loop.
At the end, if a>1 we print it as the last element.
We will keep the following invariant: at the end of the main loop the queue will always have the form:
s1 s2 ... sk 0 p1 p2 ... pl 0 p1 p2 ... pl 0
Here, p1 p2 ... pl is a prefix of the original sequence, and
s1 s2 ... sk is its remaining suffix.
In each execution of the main loop, we take several numbers from the beginning of the first sequence, and place them at the end of the second two sequences. More exactly, we will transfer up to 25 numbers in each loop.
The main loop works as follows: Get the first 25 non-zero values and store them into registers. Rotate the queue until you hit the second zero. Push the stored values, and only then push the second zero. Rotate until you hit the third zero, push the stored values again, and finally push the third zero.
In Quack code this looks as follows:
:init 0 0 0 :get >a Zaendget >b Zbendget ...... several lines omitted ...... >y Zyendget :rewind >z Zzrewind2 <z Jrewind :rewind2 0 :rewind3 >z Zzput <z Jrewind3 :put <a <b ...... several lines omitted ...... <y 0 Jrewind4 :rewind4 >z Zzput2 <z Jrewind4 :put2 <a <b ...... several lines omitted ...... <y 0 Jget :endget :lastrewind >z Zzlastput <z Jlastrewind :lastput Zalastrewind2 <a Zblastrewind2 <b ...... several lines omitted ...... Zylastrewind2 <y Jlastrewind2 :lastrewind2 >z Zzlastput2 <z Jlastrewind2 :lastput2 Zaend <a Zbend <b ...... several lines omitted ...... Zyend <y Jend :end
Note that our code handles the last iteration specially in that it checks for the first zero register and stops as soon as we hit it. We could use this same approach for all rounds. Not doing so leads to a longer program, however, this program needs slightly fewer steps.