An Unmarked Place

I present a program for determining the primality of a number on the HP 35s Programmable Calculator. Whilst this is not a particularly interesting algorithm, it should be noted that this implementation only uses the stack – no registers or variables are used whatsoever. The program uses a total of 4 entries in the stack, of which typically only one or two are directly accessible at any point in time.

The program is also intended to be relatively short. Whilst faster or shorter implementations are certainly feasible, the objective with this implementation was to use the stack exclusively, whilst not being completely naive.

The algorithm is as follows:

1. Copy the candidate prime (x) to all levels of the stack
2. Check if x is even – if it is, the number is not prime (An additional check should be performed to check if the candidate is 2, which is prime).
3. Calculate the square root of x. Take the integer portion only.
4. If the integer portion result is not odd, round to the next highest odd number. Let this be (y)
5. If the remainder of x divided by y is 0, the number is not prime. Display the canidate x and the found factor. This will be the highest factor the candidate is divisible by. End.
6. Decrease y by 2.
7. If y is greater than 1, repeat step 5.
8. The number is prime, no factors could be found. Restore x to the first position on the stack.

Few things to note:

• Complexity of this algorithm is O(√x/2)
• Despite the limited size of the stack, the expensive task of calculating the composite ceiling is only performed once.
• The largest factor of the number, as well as the original number to be tested, are preserved in the stack upon conclusion of the program.

A001  LBL A
A002  ENTER
A003  ENTER
A004  ENTER
A005  2
A006  RMDR
A007  x=0?
A008  GTO A037
A009  R↓
A010  √x
A011  IP
A012  ENTER
A013  ENTER
A014  2
A015  RMDR
A016  1
A017  +
A018  +
A019  1
A020  x=y?
A021  GTO A032
A022  R↓
A023  RMDR
A024  x=0?
A025  GTO A034
A026  LASTx
A027  2
A028  -
A029  x<>y
A030  R↓
A031  GTO A019
A032  PRIME
A033  RTN
A034  LASTx
A035  x<>y
A036  R↓
A037  NOT PRIME
A038  RTN