# Internet Problem Solving Contest

## Solution to Problem Q – QuackQuack

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.