The Museum of HP Calculators

# Prime Factorization for the HP-33s/35s

This program is by Don Shepherd and is used here by permission.

This program is supplied without representation or warranty of any kind. Don Shepherd and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

## Overview

This program determines and displays all of the prime factors of a number. The program uses the brute-force approach, so it will take a long time for large prime numbers. This program works on both the HP-33s and the HP-35s.

Enter the program as shown. To be able to run on either the 33s or 35s, the program uses several labels (A, B, C, and D). To determine the prime factors for a number, enter the number and XEQ A. On the two-line display, the top line will show a sequential number (the factor number, such as 1, 2, 3, and so on) and the bottom line will show the factor. After a brief pause, other factors are shown. You can add more PSE's at two places in the code to show the factors longer. When a zero appears on both lines, the program is done. For example, this would be the prime factorization for 24:

```24
XEQ A
1   2   3   4   0
2   2   2   3   0```

If the number you enter is a prime number, factor 1 will be the number itself.

Note: In the listing, GOTO C, for example, should be coded as GOTO C001 for the HP-35s.

Register usage:

A - current number to factor
B - test divisor
C - square root of A, upper search limit for factors
D - divisor increment (start at 1 then change to 2)
E - divisor number

## Listing

```A001  LBL A   entry point
A002  STO A   number to factor
A003  SQRT X  upper limit for factor search
A004  STO C
A005  2       test divisor, start at 2
A006  STO B
A007  1       divisor increment, start at 1 (2->3, then change to 2, 3->5, etc.)
A008  STO D
A009  STO E   divisor number, displayed on top line
B001  LBL B   begin main loop
B002  RCL A
B003  RCL B
B004  RMDR    see if B divides A evenly
B005  X!=0    B not a factor
B006  GOTO C  find next factor
B007  RCL E   B is a factor, prepare display
B008  RCL B
B009  PSE     add more PSE's if you like
B010  STO /A  update number to factor
B011  1       increment factor number
B012  STO +E
B013  RCL A
B014  SQRT X  update square root upper search limit
B015  STO C
B015  GOTO B  check factor B with new A
C001  LBL C   this divisor was not a factor
C002  RCL A
C003  1       if A=1, you are done
C004  -
C005  X=0
C006  GOTO D  search is over
C007  RCL D   divisor increment (1, initially)
C008  STO +B  add increment to test divisor
C009  2
C010  STO D   so test divisors after 2 are 3..5..7..9..
C011  RCL C   see if at SQRT(A) yet
C012  RCL B
C013  X<=Y    loop until you hit square root
C014  GOTO B
C015  RCL E   if exit loop normally, this factor is prime
C016  RCL A   setup display
C017  PSE     add more PSE's if you like
D001  LBL D   prepare screen for end signal
D002  0
D003  0
D004  RTN     program exits
```