 The Museum of HP Calculators

# Factors and Primes for the HP-67

This program is Copyright © 1976 by Hewlett-Packard and is used here by permission. This program was originally published in the HP-67 Math Pac 2.

This program is supplied without representation or warranty of any kind. Hewlett-Packard Company 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.

 Factors and Primes Shift Primes Label n→Fact From To →Primes Auto? Key A B C D E

## Overview

This program will find all prime factors of a positive integer n, or list all prime numbers between lower and upper bounds specified by the user.

A routine under LBL a is used in determining the factors of an integer n. This routine selects a trial divisor d and tests d as a factor of n. If d divides n, then n is set to n/d and d is tested as a factor of the new n. If d does not divide n, a new d is selected. The process continues until d > √n at which point n is returned as the final factor. The trial divisor d takes on the values 2,3,5,7; then for d > 10, d takes on those values that satisfy (d-10) mod 30 = 1, 3, 7, 9, 13, 19, 21, or 27. Thus in the first cycle of 30 integers from 11 to 40, d takes on the values 11, 13, 17, 19, 23, 29, 31, and 37. This technique eliminates from the test those values of d (d>10) which are divisible by 2, 3, or 5.

To list primes, a lower bound for the search must be specified. The upper bound is an optional input; if omitted, a default value of 2x109 is assumed. Upper and lower bounds need not be integers. The search for primes also uses LBL a to determine if an integer n has any factors or is indeed prime. Once an integer n (n≥3) has been tested and found to be either prime or non-prime, the next integer tested is n+2.

### Remarks:

1. The number n to be factored must be an integer in the range 0 < n ≤ 2x109. Any other input will result in a program halt with a display of "Error".
2. The upper bound of the search for primes must be greater than or equal to the lower bound, or an Error halt will occur.
3. AUTO mode is available to allow automatic output of all calculated results through PRINT/PAUSE commands. The end of all calculations is signalled by a 0.00 in the display for both modes.
4. Either routine can be quite time-consuming for large integers.

## Instructions

 Step Instructions Input Data/Units Keys Output Data/Units 1 Load side 1 and side 2. 2 To allow automatic output of results, set AUTO mode. E 1.00 3 To cancel AUTO mode later. E 0.00 4 To find factors, go to step 5; to find primes, go to step 6. FACTORS 5 Key in the integer and find its prime factors (0.00 signals end) n A Factors 0.00 PRIMES 6 Key in the lower bound of the search for primes. FROM B FROM 7 (optional) Key in the upper bound of the search (if omitted, TO = 2 x 109). TO C TO 8 Find all primes between FROM and TO (0.00 signals end of calculation). D Primes 0.00

## Examples

Find the prime factors of 924. Do not set AUTO mode.

```Keystrokes                     Outputs
924 A                           2.00
R/S                             2.00
R/S                             3.00
R/S                             7.00
R/S                            11.00
R/S                             0.00   (end)
Thus 924 = 2 x 2 x 3 x 7 x 11.
```

Find the prime factors of 3623. Do not use AUTO mode.

```Keystrokes                     Outputs
3623 A                       3623.00
R/S                             0.00   (end)
3623 is prime.
```

Find all prime numbers between 101 and 125. Use AUTO mode.

```Keystrokes                     Outputs
101 B 125 C E                   1.00   (AUTO set)
D                             101.00 ***
103.00 ***
107.00 ***
109.00 ***
113.00 ***
0.00   (end)
```

## The Program

```LINE  KEYS
001  *LBL A     Factor integer n.
002   STO B
003   ENTER↑
004   INT
005   X≠Y?      If non-integer, halt on Error.
006   GTO 5
007   0
008   STO D     Initialize d.
009   X⇔Y
010   X≤Y?      If n≤0, halt on Error.
011   GTO 5
012   2
013   EEX
014   9
015   X⇔Y
016   X>Y?
017   GTO 5     If n > 2 x 109, halt on Error.
018   CF 1      F1 clear for factors.
019   GSB a     Find factors.
020   RTN
021  *LBL B     Lower bound for primes.
022   STO A
023   X<0?      If negative, halt on Error.
024   GTO 5
025   ENTER↑    This routine finds smallest
026   INT       potential prime ≥ user's
027   X=Y?      input.
028   GTO 0
029   1
030   +
031  *LBL 0
032   2         Handle 2 as a special case
033   X⇔Y       (only even prime).
034   X=Y?
035   GTO 0
036   2
037   ÷
038   INT
039   2
040   ×
041   1
042   +
043  *LBL 0
044   STO B     Store beginning prime L.
045   STO C
046   2
047   EEX       2 x 109 is the default upper bound.
048   9
049   STO E
050   X≤Y?      If input ≥ 2 x 109, halt on Error.
051   GTO 5
052   SF 1      Flag 1 set for primes.
053   RCL A
054   RTN
055  *LBL C
056   STO A     Upper bound for primes.
057   RCL B
058   -
059   X<0?      If upper < lower, halt on Error.
060   GTO 5
061   RCL A
062   INT
063   2         Handle 2 as a special case.
064   X⇔Y
065   X=Y?
066   GTO 0
067   2
068   ÷         This routine finds the greatest potential
069   .         prime ≤ user's input.
070   5
071   +
072   INT
073   2
074   ×
075   1
076   -
077  *LBL 0
078   STO E
079   RCL A     Store final prime U.
080   RTN
081  *LBL D     Routine to list primes.
082   0
083   STO D     Initialized d←0
084   RCL B
085   2         If L = 2, print 2, add 1 and go.
086   X⇔Y
087   X=Y?
088   GTO 0
089   1         If L = 1, print 1, 2, add 1 and go.
090   X≠Y?
091   GTO 1
092   GSB e     If L ≠ 1 and L ≠ 2, go directly to LBL 1
093   +
094   RCL E
095   X⇔Y
096   X>Y?
097   GTO 4
098  *LBL 0
099   GSB e
100   1         Output 2
101   GTO 8
102  *LBL 1
103   GSB a
104   RCL B     Begin main loop.
105   RCL C     Check for factors of current n (RB).
106   X=Y?      if RB = RC, n is prime.
107   GSB e     Output n.
108   2
109  *LBL 8
110   +
111   STO C     Set n to next potential prime.
112   STO B
113   RCL E
114   X⇔Y
115   X>Y?      If n > U, exit.
116   GTO 4
117   0
118   STO D     Else loop again.
119   GTO 1
120  *LBL a     Subroutine called from both A & D which
121   2         finds factors of n.
122   GSB 3
123   X=0?
124   RTN
125   1         Check first if n is divisible by 2, 3, 5,
126   GSB 3     or 7
127   X=0?      LBL 2 check for division by integers
128   RTN       whose position in a cycle of 30 corresponds
129   2         to 11, 13, 17, 19, 23, 29, 31, or 37
130   GSB 3
131   X=0?
132   RTN
133   2
134   GSB 3
135   X=0?
136   RTN
137  *LBL 2
138   4
139   GSB 3     11 (=7+4)
140   X=0?
141   RTN
142   2
143   GSB 3     13 (=11+2)
144   X=0?
145   RTN
146   4
147   GSB 3     17 (=13+4)
148   X=0?
149   RTN
150   2
151   GSB 3     19 (=17+4)
152   X=0?
153   RTN
154   4
155   GSB 3     23 (=19+4)
156   X=0?
157   RTN
158   6
159   GSB 3     29 (=23+6)
160   X=0?
161   RTN
162   2
163   GSB 3     31 (=29+2)
164   X=0?
165   RTN
166   6
167   GSB 3     37 (=31+6)
168   X=0?
169   RTN       Loop again for next 30.
170   GTO 2
171  *LBL 3
172   RCL D     Test if d|n
173   +
174   STO D     d← d + x
175   RCL B     n
176   X⇔Y
177   ÷         n/d
178   LST X     d, n/d
179   X>Y?      If d > n/d, then d > √n
180   GTO 0     Exit.
181   X⇔Y
182   INT       [n/d] ::= INT(n/d)
183   LST X     n/d, [n/d]
184   X≠Y?      if non-integer, d does not
185   RTN       divide n.
186   STO B     Else n← n/d
187   F1?
188   CLX       If finding primes, exit.
189   F1?
190   RTN
191   RCL D     If factoring, output d.
192   GSB e
193   0         Check for d a multiple factor.
194   GTO 3
195  *LBL 0     Coming here means n is prime.
196   F1?       If finding primes, exit.
197   CLX
198   F1?
199   RTN       Else output last n.
200   RCL B
201   GSB e
202  *LBL 4
203   CLX       Exit displaying 0.
204   F0?
205   PRT SPC
206   RTN
207  *LBL E
208   F0?       Auto toggle.
209   GTO 0
210   SF 0
211   1
212   RTN
213  *LBL 0
214   CF 0
215   0
216   RTN
217  *LBL e     Output routine.
218   F0?       Print if AUTO.
219   PRTX
220   F0?
221   RTN
222   R/S       Halt if not.
223   RTN
```

## Register Use

```A   Used
B   n
C   Potential prime
D   d
E   U
```